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
topHow 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 ?
topYou 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.