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

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

top

## Abstract

top
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}\ge 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.

## How to cite

top

Alexandr 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. [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. [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. [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. [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. [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. [6] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
7. [7] E.M. Palmer, Graphical Evolution: An Introduction to the Theory of Random Graphs (Wiley, 1985). Zbl0566.05002

## NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.