Short cycles in digraphs with local average outdegree at least two

Jian Shen

The electronic journal of combinatorics, Tome 10 (2003)

Résumé

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$.

Détail

DOI : 10.37236/1719

Classification : 05C38, 05C20, 05C35