ArticleOriginal scientific text

Title

Chvátal's Condition cannot hold for both a graph and its complement

Authors 1, 2, 1

Affiliations

  1. Department of Mathematics, University of Illinois, Urbana, IL, USA
  2. Institute of Mathematics, Novosibirsk, Russia

Abstract

Chvátal's Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that di>i or dn-in-i. We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

Keywords

Hamiltonian cycle, Chvátal's Condition, random graph

Bibliography

  1. J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-136, doi: 10.1016/0012-365X(76)90078-9.
  2. V. Chvátal, On Hamilton's ideals, J. Combin. Theory (B) 12 (1972) 163-168, doi: 10.1016/0095-8956(72)90020-2.
  3. G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69.
  4. J. Gimbel, D. Kurtz, L. Lesniak, E. Scheinerman and J. Wierman, Hamiltonian closure in random graphs, Random graphs '85 (Poznań, 1985), North-Holland Math. Stud. 144 (North-Holland, 1987) 59-67.
  5. B.D. McKay and N.C. Wormald, The degree sequence of a random graph, I: The models, Random Structures and Algorithms 11 (1997) 97-117, doi: 10.1002/(SICI)1098-2418(199709)11:2<97::AID-RSA1>3.0.CO;2-O
  6. O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
  7. E.M. Palmer, Graphical Evolution: An Introduction to the Theory of Random Graphs (Wiley, 1985).
Pages:
73-76
Main language of publication
English
Received
2004-11-30
Accepted
2005-04-21
Published
2006
Exact and natural sciences