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