Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components, and (2) if n ≥ r(2a+3, a+1)+3(k-1), then G has a 2-factor with k components such that all components but one have order three.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1370,
author = {Guantao Chen and Ronald J. Gould and Ken-ichi Kawarabayashi and Katsuhiro Ota and Akira Saito and Ingo Schiermeyer},
title = {The Chv\'atal-Erd\H os condition and 2-factors with a specified number of components},
journal = {Discussiones Mathematicae Graph Theory},
volume = {27},
year = {2007},
pages = {401-407},
zbl = {1142.05064},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1370}
}
Guantao Chen; Ronald J. Gould; Ken-ichi Kawarabayashi; Katsuhiro Ota; Akira Saito; Ingo Schiermeyer. The Chvátal-Erdős condition and 2-factors with a specified number of components. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 401-407. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1370/
[000] [1] A. Bondy, A remark on two sufficient conditions for Hamilton cycles, Discrete Math. 22 (1978) 191-194, doi: 10.1016/0012-365X(78)90124-3. | Zbl 0381.05040
[001] [2] S. Brandt, G. Chen, R. Faudree, R. Gould and L. Lesniak, Degree conditions for 2-factors, J. Graph Theory 24 (1997) 165-173, doi: 10.1002/(SICI)1097-0118(199702)24:2<165::AID-JGT4>3.0.CO;2-O | Zbl 0879.05060
[002] [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (3rd ed.) (Wadsworth & Brooks/Cole, Monterey, CA, 1996).
[003] [4] V. Chvátal and P. Erdös, A note on hamiltonian circuits, Discrete Math. 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9. | Zbl 0233.05123
[004] [5] Y. Egawa, personal communication.
[005] [6] H. Enomoto, On the existence of disjoint cycles in a graph, Combinatorica 18 (1998) 487-492, doi: 10.1007/s004930050034. | Zbl 0924.05041
[006] [7] A. Kaneko and K. Yoshimoto, A 2-factor with two components of a graph satisfying the Chvátal-Erdös condition, J. Graph Theory 43 (2003) 269-279, doi: 10.1002/jgt.10119. | Zbl 1033.05085
[007] [8] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.