Improved Sufficient Conditions for Hamiltonian Properties
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 329-334
Voir la notice de l'article provenant de la source Library of Science
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},
publisher = {mathdoc},
volume = {35},
number = {2},
year = {2015},
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 PB - mathdoc 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 %I mathdoc %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/