Proof of a Conjecture of Henning and Yeo on Vertex-Disjoint Directed Cycles

Abstract

M.A. Henning and A. Yeo conjectured in SIAM J. Discrete Math., 26 (2012), pp. 687--694] that a digraph of minimum out-degree at least 4, contains two vertex-disjoint cycles of different lengths. In this paper we prove this conjecture. The main tool is a new result (to our knowledge) asserting that in a digraph $D$ of minimum out-degree at least $4$, there exist two vertex-disjoint cycles $C_1$ and $C_2$, a path $P_1$ from a vertex $x$ of $C_1$ to a vertex $z$ not in $V(C_1)\cup V(C_2)$, and a path $P_2$ from a vertex $y$ of $C_2$ to $z$, such that $V(P_1)\cap (V(C_1)\cup V(C_2))=\lbrace x\rbrace$, $V(P_2)\cap (V(C_1)\cup V(C_2))=\lbrace y\rbrace$, and $V(P_1)\cap V(P_2)=\lbrace z\rbrace$. In the last section, a conjecture will be proposed.