On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs

Ben Seamone

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 207-214
  • ISSN: 2083-5892

Abstract

top
A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note, we prove that claw-free graphs with minimum degree at least 3 are not uniquely Hamiltonian. We also show that this is best possible by exhibiting uniquely Hamiltonian claw-free graphs with minimum degree 2 and arbitrary maximum degree. Finally, we show that a construction due to Entringer and Swart can be modified to construct triangle-free uniquely Hamiltonian graphs with minimum degree 3.

How to cite

top

Ben Seamone. "On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs." Discussiones Mathematicae Graph Theory 35.2 (2015): 207-214. <http://eudml.org/doc/271097>.

@article{BenSeamone2015,
abstract = {A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note, we prove that claw-free graphs with minimum degree at least 3 are not uniquely Hamiltonian. We also show that this is best possible by exhibiting uniquely Hamiltonian claw-free graphs with minimum degree 2 and arbitrary maximum degree. Finally, we show that a construction due to Entringer and Swart can be modified to construct triangle-free uniquely Hamiltonian graphs with minimum degree 3.},
author = {Ben Seamone},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Hamiltonian cycle; uniquely Hamiltonian graphs; claw-free graphs; triangle-free graphs},
language = {eng},
number = {2},
pages = {207-214},
title = {On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs},
url = {http://eudml.org/doc/271097},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Ben Seamone
TI - On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 207
EP - 214
AB - A graph is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle. In this note, we prove that claw-free graphs with minimum degree at least 3 are not uniquely Hamiltonian. We also show that this is best possible by exhibiting uniquely Hamiltonian claw-free graphs with minimum degree 2 and arbitrary maximum degree. Finally, we show that a construction due to Entringer and Swart can be modified to construct triangle-free uniquely Hamiltonian graphs with minimum degree 3.
LA - eng
KW - Hamiltonian cycle; uniquely Hamiltonian graphs; claw-free graphs; triangle-free graphs
UR - http://eudml.org/doc/271097
ER -

References

top
  1. [1] S. Abbasi and A. Jamshed, A degree constraint for uniquely Hamiltonian graphs, Graphs Combin. 22 (2006) 433-442. doi:10.1007/s00373-006-0666-z[Crossref] Zbl1118.05055
  2. [2] H. Bielak, Chromatic properties of Hamiltonian graphs, Discrete Math. 307 (2007) 1245-1254. doi:10.1016/j.disc.2005.11.061[Crossref] 
  3. [3] J.A. Bondy and B. Jackson, Vertices of small degree in uniquely Hamiltonian graphs, J. Combin. Theory (B) 74 (1998) 265-275. doi:10.1006/jctb.1998.1845[Crossref] Zbl1026.05071
  4. [4] R.C. Entringer and H. Swart, Spanning cycles of nearly cubic graphs, J. Com- bin. Theory (B) 29 (1980) 303-309. doi:10.1016/0095-8956(80)90087-8[Crossref] Zbl0387.05017
  5. [5] H. Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J. Graph Theory 75 (2014) 167-177. doi:10.1002/jgt.2172[Crossref] Zbl1280.05074
  6. [6] P. Haxell, B. Seamone and J. Verstraete, Independent dominating sets and Hamiltonian cycles, J. Graph Theory 54 (2007) 233-244. doi:10.1002/jgt.20205[Crossref][WoS] Zbl1112.05077
  7. [7] J. Petersen, Die theorie der regul¨aren graphs, Acta Math. 15 (1891) 193-220. doi:10.1007/BF02392606[Crossref] 
  8. [8] J. Sheehan, The multiplicity of Hamiltonian circuits in a graph, in: Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Fiedler (Ed(s)), (Prague: Academia, 1975) 477-480. 
  9. [9] A.G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Dis- crete Math. 3 (1978) 259-268. doi:10.1016/S0167-5060(08)70511-9[Crossref] Zbl0382.05039
  10. [10] C. Thomassen, On the number of Hamiltonian cycles in bipartite graphs, Com- bin. Probab. Comput. 5 (1996) 437-442. doi:10.1017/S0963548300002182[Crossref] 
  11. [11] C. Thomassen, Independent dominating sets and a second Hamiltonian cycle in regular graphs, J. Combin. Theory (B) 72 (1998) 104-109. doi10.1006/jctb.1997.1794[WoS][Crossref] 
  12. [12] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946) 98-101. doi:10.1112/jlms/s1-21.2.98 [Crossref] 

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.