Geodesic
Chvátal's Condition cannot hold for both a graph and its complement
Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 1, pp. 73-76 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: Hamiltonian cycle, Chvátal's Condition, random graph 
@article{DMGT_2006_26_1_a6,
     author = {Kostochka, Alexandr and West, Douglas},
     title = {Chv\'atal's {Condition} cannot hold for both a graph and its complement},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {73--76},
     year = {2006},
     volume = {26},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a6/}
}
TY  - JOUR
AU  - Kostochka, Alexandr
AU  - West, Douglas
TI  - Chvátal's Condition cannot hold for both a graph and its complement
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2006
SP  - 73
EP  - 76
VL  - 26
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a6/
LA  - en
ID  - DMGT_2006_26_1_a6
ER  - 
%0 Journal Article
%A Kostochka, Alexandr
%A West, Douglas
%T Chvátal's Condition cannot hold for both a graph and its complement
%J Discussiones Mathematicae. Graph Theory
%D 2006
%P 73-76
%V 26
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a6/
%G en
%F DMGT_2006_26_1_a6
Kostochka, Alexandr; West, Douglas. Chvátal's Condition cannot hold for both a graph and its complement. Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 1, pp. 73-76. http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a6/

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