On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs
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 an...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2015-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1784 |
| _version_ | 1797718014512070656 |
|---|---|
| author | Seamone Ben |
| author_facet | Seamone Ben |
| author_sort | Seamone Ben |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T08:44:48Z |
| format | Article |
| id | doaj.art-583facec88b2472789a8be5b2f4bfe9a |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:48Z |
| publishDate | 2015-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-583facec88b2472789a8be5b2f4bfe9a2023-09-02T16:30:00ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922015-05-0135220721410.7151/dmgt.1784dmgt.1784On Uniquely Hamiltonian Claw-Free and Triangle-Free GraphsSeamone Ben0Department d’Informatique et de recherche opérationnelle Université de Montréal Montreal, QC, CanadaA 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.https://doi.org/10.7151/dmgt.1784hamiltonian cycleuniquely hamiltonian graphsclaw-free graphstriangle-free graphs |
| spellingShingle | Seamone Ben On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs Discussiones Mathematicae Graph Theory hamiltonian cycle uniquely hamiltonian graphs claw-free graphs triangle-free graphs |
| title | On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs |
| title_full | On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs |
| title_fullStr | On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs |
| title_full_unstemmed | On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs |
| title_short | On Uniquely Hamiltonian Claw-Free and Triangle-Free Graphs |
| title_sort | on uniquely hamiltonian claw free and triangle free graphs |
| topic | hamiltonian cycle uniquely hamiltonian graphs claw-free graphs triangle-free graphs |
| url | https://doi.org/10.7151/dmgt.1784 |
| work_keys_str_mv | AT seamoneben onuniquelyhamiltonianclawfreeandtrianglefreegraphs |