×

Disjoint cycles of different lengths in graphs and digraphs. (English) Zbl 1376.05038

Summary: In this paper, we study the question of finding a set of \(k\) vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every \(k \geqslant 1\), every graph with minimum degree at least \(\frac{k^{2}+5k-2}{2}\) has \(k\) vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider other cases such as when the graph is triangle-free, or the \(k\) cycles are required to have different lengths modulo some value \(r\). In the context of directed graphs, we consider a conjecture of Lichiardopol concerning the least minimum out-degree required for a digraph to have \(k\) vertex-disjoint directed cycles of different lengths. We verify this conjecture for tournaments, and, by using the probabilistic method, for some regular digraphs and digraphs of small order.

MSC:

05C12 Distance in graphs
05C07 Vertex degrees
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] N. Alon. Disjoint directed cycles. Journal of Combinatorial Theory, Series B, 68(2):167-178, 1996. · Zbl 0861.05037
[2] S. Bessy, N. Lichiardopol and J.-S. Sereni. Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree. Discrete Mathematics, 310(3):557-560, 2009. · Zbl 1188.05072
[3] J.-C. Bermond and C. Thomassen. Cycles in digraphs – a survey. Journal of Graph Theory, 5(1):1-43, 1981. · Zbl 0458.05035
[4] P. Camion. Chemins et circuits hamiltoniens des graphes complets. Comptes Rendus de l’Acad´emie des Sciences de Paris, 249:2151-2152, 1959. · Zbl 0092.15801
[5] A.A. Diwan. Decomposing graphs with girth at least five under degree constraints. Journal of Graph Theory, 33:237-239, 2000. · Zbl 0942.05055
[6] A.A. Diwan. Cycles of even lengths modulo k. Journal of Graph Theory, 65(3):246 253, 2010. · Zbl 1238.05150
[7] G.A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathe matical Society, S3-2(1):69-81, 1952. · Zbl 0047.17001
[8] M.A. Henning and A. Yeo. Vertex Disjoint Cycles of Different Length in Digraphs. SIAM Journal on Discrete Mathematics, 26:687-694, 2012. · Zbl 1248.05079
[9] A. Kaneko. On decomposition of triangle-free graphs under degree constraints. Jour nal of Graph Theory, 27:7-9, 1998. · Zbl 0892.05040
[10] N. Lichiardopol. Proof of a Conjecture of Henning and Yeo on Vertex-Disjoint Di rected Cycles. SIAM Journal on Discrete Mathematics, 28(3):1618-1627, 2014. · Zbl 1305.05109
[11] N. Lichiardopol, A. P´or and J.-S. Sereni. A Step toward the Bermond-Thomassen Conjecture about Disjoint Cycles in Digraphs. SIAM Journal on Discrete Mathemat ics, 23(2):979-992, 2009. · Zbl 1191.05054
[12] J.W. Moon. Topics on Tournaments. Holt, Rinehart and Winston, New York, 1968. · Zbl 0191.22701
[13] M. Molloy and B. Reed. Graph Colouring and the Probabilistic Method. Springer, 2002. · Zbl 0987.05002
[14] M. Stiebitz. Decomposing graphs under degree constraints. Journal of Graph Theory, 23(3):321-324, 1996. · Zbl 0865.05058
[15] C. Thomassen. 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.