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

Alexandr V. Kostochka; Douglas B. West

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 1, page 73-76
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAlexandr V. Kostochka, and Douglas B. West. "Chvátal's Condition cannot hold for both a graph and its complement." Discussiones Mathematicae Graph Theory 26.1 (2006): 73-76. <http://eudml.org/doc/270338>.

@article{AlexandrV2006,

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 $d_i > i$ or $d_\{n-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.},

author = {Alexandr V. Kostochka, Douglas B. West},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Hamiltonian cycle; Chvátal's Condition; random graph; cycle; probability},

language = {eng},

number = {1},

pages = {73-76},

title = {Chvátal's Condition cannot hold for both a graph and its complement},

url = {http://eudml.org/doc/270338},

volume = {26},

year = {2006},

}

TY - JOUR

AU - Alexandr V. Kostochka

AU - Douglas B. West

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

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 1

SP - 73

EP - 76

AB - 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 $d_i > i$ or $d_{n-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.

LA - eng

KW - Hamiltonian cycle; Chvátal's Condition; random graph; cycle; probability

UR - http://eudml.org/doc/270338

ER -

## References

top- [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. Zbl0331.05138
- [2] V. Chvátal, On Hamilton's ideals, J. Combin. Theory (B) 12 (1972) 163-168, doi: 10.1016/0095-8956(72)90020-2. Zbl0213.50803
- [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. Zbl0047.17001
- [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. Zbl0634.05039
- [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 Zbl0884.05081
- [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). Zbl0566.05002

## NotesEmbed ?

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