On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs

• Autorzy: Ben Seamone
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Hamiltonian cycle; uniquely Hamiltonian graphs; claw-free graphs; triangle-free graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 2
• Strony: 207-214

Daty

wydano

2015-05-01

poprawiono

2014-04-02

zaakceptowano

2014-04-02

online

2015-04-18

otrzymano

2020-01-20

Twórcy

autor

Ben Seamone

• Department d’Informatique et de recherche opérationnelle Université de Montréal Montreal, QC, Canada

Bibliografia

• [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]
• [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]
• [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]
• [5] H. Fleischner, Uniquely Hamiltonian graphs of minimum degree 4, J. Graph Theory 75 (2014) 167-177. doi:10.1002/jgt.2172[Crossref]
• [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]
• [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]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1784