Discussiones Mathematicae Graph Theory 27(3) (2007) 401-407
doi: 10.7151/dmgt.1370

[BIBTex] [PDF] [PS]

THE CHVÁTAL-ERDOS CONDITION AND 2-FACTORS WITH A SPECIFIED NUMBER OF COMPONENTS

Guantao Chen

Department of Mathematics and Statistics
Georgia State University, Atlanta, GA 30303, USA

Ronald J. Gould

Department of Mathematics and Computer Science
Emory University, Atlanta, GA 30322, USA

Ken-ichi Kawarabayashi

National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-Ku, Tokyo 101-8430, Japan

Katsuhiro Ota

Department of Mathematics, Keio University
3-14-1 Hiyoshi, Kohoku-Ku, Yokohama 223-8522, Japan

Akira Saito

Department of Computer Science, Nihon University
Sakurajosui 3-25-40, Setagaya-Ku, Tokyo 156-8550, Japan

Ingo Schiermeyer

Institut für Diskrete Mathematik und Algebra
Technische Universität
Bergakademie Freiberg, D-09596 Freiberg, Germany

Abstract

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.

The Chvátal-Erdös Condition and 2-Factors with ...

Keywords: Chvátal-Erdös condition, 2-factor, hamiltonian cycle, Ramsey number.

2000 Mathematics Subject Classification: Primary: 05C38; Secondary: 05C40, 05C45, 05C69.

References

[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.
[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.
[3] G. Chartrand and L. Lesniak, Graphs & Digraphs (3rd ed.) (Wadsworth & Brooks/Cole, Monterey, CA, 1996).
[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.
[5] Y. Egawa, personal communication.
[6] H. Enomoto, On the existence of disjoint cycles in a graph, Combinatorica 18 (1998) 487-492, doi: 10.1007/s004930050034.
[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.
[8] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.

Received 1 March 2006
Revised 23 July 2007
Accepted 23 July 2007