×

Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree. (English) Zbl 1188.05072

In 1981, J.C. Bermond and C. Thomassen [“Cycles in digraphs. A survey”, J. Graph Theory 5, 1–43 (1981; Zbl 0458.05035)] conjectured that for any positive integer \(r\), any digraph of minimum out-degree at least \(2r - 1\) contains at least r vertex-disjoint directed cycles. It can be shown that the conjecture is true for \(r = 2\) and \(3\), and that a \(k\)-strongly-connected tournament of order at least \(5k - 3\) contains \(k\) vertex-disjoint directed cycles. The present note gives two proofs of this conjecture for tournaments with minimum in-degree at least \(2r - 1\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles

Citations:

Zbl 0458.05035
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bang-Jensen, J.; Gutin, G., Digraphs. Theory, Algorithms and Applications (2001), Springer-Verlag London Ltd: Springer-Verlag London Ltd London · Zbl 0958.05002
[2] Bermond, J.-C.; Thomassen, C., Cycles in digraphs—a survey, J. Graph Theory, 5, 1, 1-43 (1981) · Zbl 0458.05035
[3] Chen, G.; Gould, R. J.; Li, H., Partitioning vertices of a tournament into independent cycles, J. Combin. Theory Ser. B, 83, 2, 213-220 (2001) · Zbl 1028.05038
[4] Li, H.; Shu, J., The partition of a strong tournament, Discrete Math., 290, 2-3, 211-220 (2005) · Zbl 1069.05037
[5] N. Lichiardopol, Dominated and dominating arcs in tournaments. Vertex strong connectivity of doubly regular tournaments (submitted for publication); N. Lichiardopol, Dominated and dominating arcs in tournaments. Vertex strong connectivity of doubly regular tournaments (submitted for publication)
[6] N. Lichiardopol, A. Pór, J.-S. Sereni, A step towards the Bermond-Thomassen conjecture about disjoint cycles in digraphs, SIAM J. Discrete Math. (in press). ITI Series 2007-339; N. Lichiardopol, A. Pór, J.-S. Sereni, A step towards the Bermond-Thomassen conjecture about disjoint cycles in digraphs, SIAM J. Discrete Math. (in press). ITI Series 2007-339
[7] Thomassen, C., Disjoint cycles in digraphs, Combinatorica, 3, 3-4, 393-396 (1983) · Zbl 0527.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.