# The Chvátal-Erdős condition and 2-factors with a specified number of components

• Volume: 27, Issue: 3, page 401-407
• ISSN: 2083-5892

top

## Abstract

top
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.

## How to cite

top

Guantao Chen, et al. "The Chvátal-Erdős condition and 2-factors with a specified number of components." Discussiones Mathematicae Graph Theory 27.3 (2007): 401-407. <http://eudml.org/doc/270518>.

@article{GuantaoChen2007,
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.},
author = {Guantao Chen, Ronald J. Gould, Ken-ichi Kawarabayashi, Katsuhiro Ota, Akira Saito, Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Chvátal-Erdös condition; 2-factor; hamiltonian cycle; Ramsey number; Chvátal-Erdős condition},
language = {eng},
number = {3},
pages = {401-407},
title = {The Chvátal-Erdős condition and 2-factors with a specified number of components},
url = {http://eudml.org/doc/270518},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Guantao Chen
AU - Ronald J. Gould
AU - Ken-ichi Kawarabayashi
AU - Katsuhiro Ota
AU - Akira Saito
AU - Ingo Schiermeyer
TI - The Chvátal-Erdős condition and 2-factors with a specified number of components
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 401
EP - 407
AB - 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.
LA - eng
KW - Chvátal-Erdös condition; 2-factor; hamiltonian cycle; Ramsey number; Chvátal-Erdős condition
UR - http://eudml.org/doc/270518
ER -

## References

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

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.