On the girth of digraphs Original Research Article

It was conjectured by Caccetta and Häggkvist in 1978 that the girth of every digraph with n vertices and minimum outdegree r is at most ⌈n/r⌉. The conjecture was proved for r=2 by Caccetta and Häggkvist, for r=3 by Hamidoune and for r=4,5 by Hoáng and Reed. In this paper, the following two main results are proved: 1. The diameter of every strongly connected digraph of order n with girth g is at most n−g+t, where t is the number of vertices having outdegree exactly 1. As a consequence, a short, self-contained proof of Caccetta and Häggkvistʹs result is obtained. 2. The girth of every digraph with n vertices and minimum outdegree r is at most max{⌈n/r⌉,2r−2}. As a consequence, the above conjecture is proved for the case n⩾2r2−3r+1. In other words, for each given r, the number of counterexamples to the conjecture, if any, is finite.