Improved Sufficient Conditions for Hamiltonian Properties

Jens-P. Bode; Anika Fricke; Arnfried Kemnitz

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 329-334
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Jens-P. Bode, Anika Fricke, and Arnfried Kemnitz. "Improved Sufficient Conditions for Hamiltonian Properties." Discussiones Mathematicae Graph Theory 35.2 (2015): 329-334. <http://eudml.org/doc/271094>.

@article{Jens2015,
abstract = {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.},
author = {Jens-P. Bode, Anika Fricke, Arnfried Kemnitz},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Hamiltonian; traceable; Hamiltonian-connected; Hamiltonian cycle; traceable graphs; Hamiltonian-connected graphs},
language = {eng},
number = {2},
pages = {329-334},
title = {Improved Sufficient Conditions for Hamiltonian Properties},
url = {http://eudml.org/doc/271094},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Jens-P. Bode
AU - Anika Fricke
AU - Arnfried Kemnitz
TI - Improved Sufficient Conditions for Hamiltonian Properties
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 329
EP - 334
AB - 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.
LA - eng
KW - Hamiltonian; traceable; Hamiltonian-connected; Hamiltonian cycle; traceable graphs; Hamiltonian-connected graphs
UR - http://eudml.org/doc/271094
ER -

References

top
  1. [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. Zbl1229.05191
  2. [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. [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[Crossref] Zbl0331.05138
  4. [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[Crossref] 
  5. [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[Crossref] Zbl0047.17001
  6. [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. [7] O. Ore, Note on Hamiltonian circuits, Amer. Math. Monthly 67 (1960) 55. 
  8. [8] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27. Zbl0106.37103

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.