Abstract
We prove that if G is a graph of order at least 2k with k ⩾ 9 and the minimum degree of G is at least k + 1, then G contains two vertex-disjoint cycles of order at least k. Moreover, the condition on the minimum degree is sharp.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Berstel J, Perrin D. Theory of Codes. Orlando: Academic Press, 1985
Reis C M, Shyr H J. Some properties of disjunctive languages on a free monoid. Inform Contr, 1978, 37: 334–344
Bollobá B. Extremal Graph Theory. London: Academic Press, 1978
Bondy J. Pancyclic graphs I. J Combin Theory Ser B, 1971, 11: 80–84
Bondy J, Chvátal V. A method in graph theory. Discrete Math, 1976, 15: 111–135
Corrádi K, Hajnal A. On the maximal number of independent circuits in a graph. Acta Math Acad Sci Hungar, 1963, 14: 423–439
Dirac G A. Some theorems on abstract graphs. Proc London Math Soc, 1952, 2: 69–81
Egawa Y, Glas R, Locke S C. Cycles and paths through specified vertices in k-connected graphs. J Combin Theory Ser B, 1991, 52: 20–29
El-Zahar M H. On circuits in graphs. Discrete Math, 1984, 50: 227–230
Erdős P, Gallai T. On maximal paths and circuits of graphs. Acta Math Acad Sci Hungar, 1959, 10: 337–356
Ore O. Note on Hamilton circuits. Amer Math Monthly, 1960, 67: 55
Wang H. Independent cycles with limited size in a graph. Graphs Combin, 1994, 10: 271–281
Wang H. Two vertex-disjoint cycles in a graph. Graphs Combin, 1995, 11: 389–396
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, H. Disjoint long cycles in a graph. Sci. China Math. 56, 1983–1998 (2013). https://doi.org/10.1007/s11425-012-4539-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-012-4539-z