Short Cycles in Digraphs with Local Average Outdegree at Least Two

Abstract

Suppose $G$ is a strongly connected digraph with order $n$ girth $g$ and diameter $d$. We prove that $d +g \le n$ if $G$ contains no arcs $(u,v)$ with $\deg^+(u)=1$ and $\deg^+(v) \le 2$.

Caccetta and H${\rm\ddot{a}}$ggkvist showed in 1978 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 $\deg^+(u) +\deg^+(v) \ge 4$ for all arcs $(u,v)$, or

(2) $\deg^+(u) +\deg^+(v) \ge 3$ for all pairs of distinct vertices $u,v$,

then $G$ contains a cycle of length at most $\lceil n/2 \rceil$.