Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 687-694 |
Number of pages | 8 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 26 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2012 |
Keywords
- Digraphs
- Vertex disjoint cycles
ASJC Scopus subject areas
- General Mathematics