# On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs

Discussiones Mathematicae Graph Theory (2015)

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

## Access Full Article

top## Abstract

top## How to cite

topBen 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] 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] H. Bielak, Chromatic properties of Hamiltonian graphs, Discrete Math. 307 (2007) 1245-1254. doi:10.1016/j.disc.2005.11.061[Crossref]
- [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] 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] 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] 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] J. Petersen, Die theorie der regul¨aren graphs, Acta Math. 15 (1891) 193-220. doi:10.1007/BF02392606[Crossref]
- [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] 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] 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] 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] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946) 98-101. doi:10.1112/jlms/s1-21.2.98 [Crossref]

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.