Vertex Disjoint Cycles of Different Length in Digraphs
Michael A. Henning, Anders Yeo · SIAM Journal on Discrete Mathematics · 2012
Thomassen [Combinatorica, 3 (1983), pp. 393–396] proved that every digraph with minimum out-degree at least three has two vertex disjoint cycles. There are examples of 3-regular digraphs where all pairs of vertex disjoint cycles have the same length. In this paper we raise the conjectures that all 3-regular bipartite digraphs and all digraphs with minimum degree at least four have two vertex disjoint cycles of different length. We give support for our conjectures by proving that all 4-regular digraphs do indeed have two vertex disjoint cycles of different length. We furthermore discuss consequences of our results and conjectures as well as arc-weighted versions of our conjecture.