Back to Search
Start Over
ON THE NUMBER OF VERTEX-DISJOINT CYCLES IN DIGRAPHS.
- Source :
- SIAM Journal on Discrete Mathematics; 2019, Vol. 33 Issue 4, p2444-2451, 8p
- Publication Year :
- 2019
-
Abstract
- Let k be a positive integer. Bermond and Thomassen conjectured in 1981 that every digraph with minimum outdegree at least 2k 1 contains k vertex-disjoint cycles. This conjecture is famous as one of a hundred unsolved problems selected in [A. Bondy and M. R. Murty, Graph Theory, Springer-Verlag, London, 2008]. Lichiardopol, P\'or, and Sereni proved in [SIAM J. Discrete Math., 23 (2009), pp. 979--992] that the above conjecture holds for k = 3. Let g be the girth, i.e., the length of the shortest cycle, of a given digraph. Bang-Jensen, Bessy, and Thomass\'e conjectured in [J. Graph Theory, 75 (2014), pp. 284--302] that every digraph with girth g and minimum outdegree at least g g 1 k contains k vertex-disjoint cycles. Thomass\'e conjectured around 2006 that every oriented graph (a digraph without 2-cycles) with girth g and minimum outdegree at least h contains a path of length h(g 1), where h is a positive integer. In this paper, we first present a new shorter proof of the Bermond--Thomassen conjecture for the case of k = 3, and then we disprove the conjecture proposed by Bang-Jensen, Bessy, and Thomass\'e. Finally, we disprove the even girth case of the conjecture proposed by Thomass\'e. [ABSTRACT FROM AUTHOR]
- Subjects :
- DIRECTED graphs
GRAPH theory
LOGICAL prediction
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 33
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 144662498
- Full Text :
- https://doi.org/10.1137/18M1186356