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.
@article{bwmeta1.element.doi-10_7151_dmgt_1784,
author = {Ben Seamone},
title = {On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {207-214},
zbl = {1311.05104},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1784}
}
Ben Seamone. On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 207-214. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1784/
[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] | Zbl 1118.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] | Zbl 1026.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] | Zbl 0387.05017
[5] H. Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J. Graph Theory 75 (2014) 167-177. doi:10.1002/jgt.2172[Crossref] | Zbl 1280.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] | Zbl 1112.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] | Zbl 0382.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]