Geodesic
Improved Sufficient Conditions for Hamiltonian Properties
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 329-334 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In 1980 Bondy [2] proved that a (k+s)-connected graph of order n ≥ 3 is traceable (s = −1) or Hamiltonian (s = 0) or Hamiltonian-connected (s = 1) if the degree sum of every set of k+1 pairwise nonadjacent vertices is at least ((k+1)(n+s−1)+1)/2. It is shown in [1] that one can allow exceptional (k+1)-sets violating this condition and still implying the considered Hamiltonian property. In this note we generalize this result for s = −1 and s = 0 and graphs that fulfill a certain connectivity condition.
Keywords: Hamiltonian, traceable, Hamiltonian-connected 
@article{DMGT_2015_35_2_a10,
     author = {Bode, Jens-P. and Fricke, Anika and Kemnitz, Arnfried},
     title = {Improved {Sufficient} {Conditions} for {Hamiltonian} {Properties}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {329--334},
     year = {2015},
     volume = {35},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a10/}
}
TY  - JOUR
AU  - Bode, Jens-P.
AU  - Fricke, Anika
AU  - Kemnitz, Arnfried
TI  - Improved Sufficient Conditions for Hamiltonian Properties
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 329
EP  - 334
VL  - 35
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a10/
LA  - en
ID  - DMGT_2015_35_2_a10
ER  - 
%0 Journal Article
%A Bode, Jens-P.
%A Fricke, Anika
%A Kemnitz, Arnfried
%T Improved Sufficient Conditions for Hamiltonian Properties
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 329-334
%V 35
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a10/
%G en
%F DMGT_2015_35_2_a10
Bode, Jens-P.; Fricke, Anika; Kemnitz, Arnfried. Improved Sufficient Conditions for Hamiltonian Properties. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 329-334. http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a10/

[1] J.-P. Bode, A. Kemnitz, I. Schiermeyer and A. Schwarz, Generalizing Bondy’s theorems on sufficient conditions for Hamiltonian properties, Congr. Numer. 203 (2010) 5-13.

[2] J.A. Bondy, Longest paths and cycles in graphs of high degree, Research Report CORR 80-16 (Department of Combinatorics and Optimization, Faculty of Mathe- matics, University of Waterloo, Waterloo, Ontario, Canada, 1980).

[3] J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-135. doi:10.1016/0012-365X(76)90078-9

[4] V. Chvátal and P. Erdős, A note on Hamiltonian circuits, Discrete Math. 2 (1972) 111-113. doi:10.1016/0012-365X(72)90079-9

[5] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. s3-2 (1952) 69-81. doi:10.1112/plms/s3-2.1.69

[6] P. Fraisse, Dλ-cycles and their applications for Hamiltonian graphs (LRI, Rapport de Recherche 276, Centre d’Orsay, Université de Paris-Sud, 1986).

[7] O. Ore, Note on Hamiltonian circuits, Amer. Math. Monthly 67 (1960) 55.

[8] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27.