PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 2 | 207-214
Tytuł artykułu

On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs

Autorzy
Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
35
Numer
2
Strony
207-214
Opis fizyczny
Daty
wydano
2015-05-01
poprawiono
2014-04-02
zaakceptowano
2014-04-02
online
2015-04-18
otrzymano
2020-01-20
Twórcy
autor
  • Department d’Informatique et de recherche opérationnelle Université de Montréal Montreal, QC, Canada, seamone@iro.umontreal.ca
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1784
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.