Geodesic
On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 207-214.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: Hamiltonian cycle, uniquely Hamiltonian graphs, claw-free graphs, triangle-free graphs 
@article{DMGT_2015_35_2_a0,
     author = {Seamone, Ben},
     title = {On {Uniquely} {Hamiltonian} {Claw-Free} and {Triangle-Free} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {207--214},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a0/}
}
TY  - JOUR
AU  - Seamone, Ben
TI  - On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 207
EP  - 214
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a0/
LA  - en
ID  - DMGT_2015_35_2_a0
ER  - 
%0 Journal Article
%A Seamone, Ben
%T On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 207-214
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a0/
%G en
%F DMGT_2015_35_2_a0
Seamone, Ben. On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 207-214. http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a0/

[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

[2] H. Bielak, Chromatic properties of Hamiltonian graphs, Discrete Math. 307 (2007) 1245-1254. doi:10.1016/j.disc.2005.11.061

[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

[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

[5] H. Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J. Graph Theory 75 (2014) 167-177. doi:10.1002/jgt.2172

[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

[7] J. Petersen, Die theorie der regul¨aren graphs, Acta Math. 15 (1891) 193-220. doi:10.1007/BF02392606

[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

[10] C. Thomassen, On the number of Hamiltonian cycles in bipartite graphs, Com- bin. Probab. Comput. 5 (1996) 437-442. doi:10.1017/S0963548300002182

[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

[12] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946) 98-101. doi:10.1112/jlms/s1-21.2.98