文摘
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 c3017a883f55f96b6a9f979677f" title="Click to view the MathML source">Δ 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 14ca6e324d7290a4f0fefb70bf7b75f" title="Click to view the MathML source">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.