Back to Search
Start Over
VERTEX DISJOINT CYCLES OF DIFFERENT LENGTH IN DIGRAPHS.
- Source :
-
SIAM Journal on Discrete Mathematics . 2012, Vol. 26 Issue 2, p687-694. 8p. 1 Diagram. - Publication Year :
- 2012
-
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 [ABSTRACT FROM AUTHOR]
- Subjects :
- *DIRECTED graphs
*INTEGRAL theorems
*HYPERGRAPHS
*MATHEMATICS
*GRAPH theory
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 26
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 80535671
- Full Text :
- https://doi.org/10.1137/100802463