The diameter of directed graphs (Q1775900): Difference between revisions

Let \(D\) be a strongly connected Eulerian oriented graph with \(n\) vertices and minimum out-degree \(\delta\). The author shows that the diameter of \(D\) is at most \(4n/(2\delta+ 1)+ 2\). This bound, which strengthens an earlier bound by \textit{A. V. Knyazev} [Mat. Zametki 41, 829--843, 891 (1987; Zbl 0698.05045)], is sharp apart from an additive constant.