PROOF OF A CONJECTURE OF HENNING AND YEO ON VERTEX-DISJOINT DIRECTED CYCLES

摘要

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) U V(C_2), and a path P_2 from a vertex y of C_2 to z, such that V{P_1) ∩ (V(C_1) ∪V(C_2)) = {x}, V{P_2) ∩ (V(C_1)∪ V{C_2)) = {g}, and V(P_1) ∩ V(P_2) = {z}. In the last section, a conjecture will be proposed.