In this paper we consider upper bounds on the diameter of Eulerian digraphs containing a vertex of large degree. Define the maximum degree of a digraph to be the maximum of all in-degrees and out-degrees of its vertices. We show that the diameter of an Eulerian digraph of order n and maximum degree Δ is at most n - Δ + 3 , and this bound is sharp. We also show that the bound can be improved for Eulerian digraphs with no 2-cycle to n - 2 Δ + O ( Δ 2 / 3 ) , and we exhibit an infinite family of such digraphs of diameter n - 2 Δ + ? ( Δ 1 / 2 ) . We further show that for bipartite Eulerian digraphs with no 2-cycle the diameter is at most n - 2 Δ + 3 , and that this bound is sharp.
['Peter Dankelmann', 'Michael J. Dorfling']
Diameter and maximum degree in Eulerian digraphs