Chvátal's Condition cannot hold for both a graph and its complement
Alexandr V. Kostochka ; Douglas B. West
Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 73-76 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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

Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:270338 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1302,
     author = {Alexandr V. Kostochka and Douglas B. West},
     title = {Chv\'atal's Condition cannot hold for both a graph and its complement},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {73-76},
     zbl = {1104.05019},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1302}
}

Alexandr V. Kostochka; Douglas B. West. Chvátal's Condition cannot hold for both a graph and its complement. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 73-76. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1302/

[000] [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. | Zbl 0331.05138

[001] [2] V. Chvátal, On Hamilton's ideals, J. Combin. Theory (B) 12 (1972) 163-168, doi: 10.1016/0095-8956(72)90020-2. | Zbl 0213.50803

[002] [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. | Zbl 0047.17001

[003] [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. | Zbl 0634.05039

[004] [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 | Zbl 0884.05081

[005] [6] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.

[006] [7] E.M. Palmer, Graphical Evolution: An Introduction to the Theory of Random Graphs (Wiley, 1985). | Zbl 0566.05002