On the girth of digraphs (Q1969785): Difference between revisions

Let \(G\) denote a strongly-connected digraph with \(n\) nodes, girth \(g\), and diameter \(D\). The author shows that if \(G\) has \(t\) nodes of out-degree one, then \(D\leq n-g+ t\). He also shows that if \(r\) denotes the minimum out-degree of \(G\), then \(g\leq \max\{\lceil n/r\rceil, 2r- 2\}\). This last result implies that when \(n\geq 2r^2- 3r+ 1\), then the conjecture of \textit{L. Caccetta} and \textit{R. Häggkvist} [Proc. 9th Southeast Conference on Combinatorics, graph theory and computing, Boca Raton 1978, 181-187 (1978; Zbl 0406.05033)] holds, namely, that \(g\leq \lceil n/r\rceil\).