DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 26(1) (2006) 73-76
DOI: 10.7151/dmgt.1302

CHVÁTAL'S CONDITION CANNOT HOLD FOR BOTH A GRAPH AND ITS COMPLEMENT

Alexandr V. Kostochka

Department of Mathematics
University of Illinois, Urbana, IL, USA
and
Institute of Mathematics, Novosibirsk, Russia
e-mail: kostochk@math.uiuc.edu

Douglas B. West

Department of Mathematics
University of Illinois, Urbana, IL, USA
e-mail: west@math.uiuc.edu

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 d1, ...,dn in nondecreasing order, i < n/2 implies that di > i or dn−i ≥ n−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.

2000 Mathematics Subject Classification: 05C45, 05C07, 05C80.

References

[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).

Received 30 November 2004
Revised 21 April 2005