On short cycles in triangle-free oriented graphs

Ji, Yurong ; Wu, Shufei ; Song, Hui

Czechoslovak Mathematical Journal, Tome 68 (2018) no. 1, pp. 67-75.

Résumé

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $\lceil n / d\rceil $. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that $\alpha _0$ is the smallest real such that every $n$-vertex digraph with minimum outdegree at least $\alpha _0n$ contains a directed triangle. Let $\epsilon {(3-2\alpha _0)}/{(4-2\alpha _0)}$ be a positive real. We show that if $D$ is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least $(1/{(4-2\alpha _0)}+\epsilon )|D|$, then each vertex of $D$ is contained in a directed cycle of length $l$ for each $4\le l {(4-2\alpha _0)\epsilon |D|}/{(3-2\alpha _0)}+2$.

Détail

DOI : 10.21136/CMJ.2017.0131-16

Classification : 05C20, 05C38
Keywords: oriented graph; cycle; minimum semidegree