Short Cycles in Digraphs with Local Average Outdegree at Least Two - Shen, Jian (The Electronic Journal of Combinatorics, 2003)
Suppose G is a strongly connected digraph with order n girth g and diameter d. We prove that d +g n if G contains no arcs (u,v) with ^+(u)=1 and ^+(v) 2. Caccetta and Ha ggkvist showed in 1978 that any digraph of order n with minimum outdegree 2 contains a cycle of length at most n/2 ceil. Applying the above-mentioned result, we improve their result by replacing the minimum outdegree condition by some weaker conditions involving the local average outdegree. In particular, we prove that, for any digraph G of order n, if either (1) G has minimum outdegree 1 and ^+(u) +^+(v) 4 for all arcs (u,v), or (2) ^+(u) +^+(v) 3 for all pairs of distinct vertices u,v, then G contains a cycle of length at most n/2 ceil.