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

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 -