Download PDF - The Chvátal-Erdős condition and 2-factors with a specified number of componentsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1, 2, 3, 4, 5,

Affiliations

  1. Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, USA
  2. Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA
  3. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-Ku, Tokyo 101-8430, Japan
  4. Department of Mathematics, Keio University, 3-14-1 Hiyoshi, Kohoku-Ku, Yokohama 223-8522, Japan
  5. Department of Computer Science, Nihon University, Sakurajosui 3-25-40, Setagaya-Ku, Tokyo 156-8550, Japan
  6. 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.

Keywords

ENG
Chvátal-Erdös condition, 2-factor, hamiltonian cycle, Ramsey number

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2007/27/3
Export to PBN, Opens in new tab
Pages:
401-407
Main language of publication
English
Received
2006-03-01
Accepted
2007-07-23
Published
2007

DOI: 10.7151/dmgt.1370

Exact and natural sciences