Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9516180 | Journal of Combinatorial Theory, Series B | 2005 | 4 Pages |
Abstract
Let D be a strongly connected oriented graph, i.e., a digraph with no cycles of length 2, of order n and minimum out-degree δ. Let D be eulerian, i.e., the in-degree and out-degree of each vertex are equal. Knyazev (Mat. Z. 41(6) 1987 829) proved that the diameter of D is at most 52δ+2n and, for given n and δ, constructed strongly connected oriented graphs of order n which are δ-regular and have diameter greater than 42δ+1n-4. We show that Knyazev's upper bound can be improved to diam(D)⩽42δ+1n+2, and this bound is sharp apart from an additive constant.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Peter Dankelmann,