Uniquely hamiltonian graphs for many sets of degrees
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909413585977344 |
|---|---|
| author | Brinkmann, Gunnar De Pauw, Matthias |
| author_facet | Brinkmann, Gunnar De Pauw, Matthias |
| contents | We give constructive proofs for the existence of uniquely hamiltonian graphs for various sets of degrees. We give constructions for all sets with minimum 2 (a trivial case added for completeness), all sets with minimum 3 that contain an even number (for sets without an even number it is known that no uniquely hamiltonian graphs exist), and all sets with minimum 4, except {4}, {4,5}, and {4,6}. For minimum degree 3 and 4, the constructions also give 3-connected graphs. We also introduce the concept of seeds, which makes the above results possible and might be useful in the study of Sheehan's conjecture. Furthermore, we prove that 3-connected uniquely hamiltonian 4-regular graphs exist if and only if 2-connected uniquely hamiltonian 4-regular graphs exist. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_08946 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Uniquely hamiltonian graphs for many sets of degrees Brinkmann, Gunnar De Pauw, Matthias Combinatorics 05C45 We give constructive proofs for the existence of uniquely hamiltonian graphs for various sets of degrees. We give constructions for all sets with minimum 2 (a trivial case added for completeness), all sets with minimum 3 that contain an even number (for sets without an even number it is known that no uniquely hamiltonian graphs exist), and all sets with minimum 4, except {4}, {4,5}, and {4,6}. For minimum degree 3 and 4, the constructions also give 3-connected graphs. We also introduce the concept of seeds, which makes the above results possible and might be useful in the study of Sheehan's conjecture. Furthermore, we prove that 3-connected uniquely hamiltonian 4-regular graphs exist if and only if 2-connected uniquely hamiltonian 4-regular graphs exist. |
| title | Uniquely hamiltonian graphs for many sets of degrees |
| topic | Combinatorics 05C45 |
| url | https://arxiv.org/abs/2304.08946 |