Abstract
Soares [J. Graph Theory 1992] showed that the well known upper bound on the diameter of undirected graphs of order n and minimum degree δ also holds for digraphs, provided they are eulerian. In this paper we investigate if similar bounds can be given for digraphs that are, in some sense, close to being eulerian. In particular we show that a directed graph of order n and minimum degree δ whose arc set can be partitioned into s trails, where s ≤ - 2, has diameter at most. If s also divides δ - 2, then we show the diameter to be at most. The latter bound is sharp, apart from an additive constant. As a corollary we obtain the sharp upper bound on the diameter of digraphs that have an eulerian trail.
Original language | English |
---|---|
Journal | Electronic Journal of Combinatorics |
Volume | 17 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2010 |
Externally published | Yes |
Keywords
- Diameter
- Digraph
- Eulerian
- Semi-eulerian
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics