Short cycles in digraphs with local average outdegree at least two (Q1408530)

Summary: Suppose \(G\) is a strongly connected digraph with order \(n\), girth \(g\) and diameter \(d\). We prove that \(d+g \leq n\) if \(G\) contains no arcs \( (u,v)\) with \(\text{deg}^+(u)=1\) and \(\text{deg}^+(v) \leq 2\). \textit{L. Caccetta} and \textit{R. Häggkvist} [Proc. 9th southeast Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 181-187 (1978; Zbl 0406.05033)] showed that any digraph of order \(n\) with minimum outdegree \(2\) contains a cycle of length at most \(\lceil n/2\rceil\). 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 \(\text{deg}^+(u) + \text{deg}^+(v) \geq 4\) for all arcs \((u,v)\), or (2) \(\text{deg}^+(u) + \text{deg}^+(v) \geq 3\) for all pairs of distinct vertices \(u,v\), then \(G\) contains a cycle of length at most \(\lceil n/2\rceil\).