Symmetry classes of Hamiltonian cycles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918483397181440 |
|---|---|
| author | Baligacs, Julia Brenner, Sofia Lutz, Annette Volk, Lena |
| author_facet | Baligacs, Julia Brenner, Sofia Lutz, Annette Volk, Lena |
| contents | We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs where, for every pair of Hamiltonian cycles, there is a graph automorphism mapping one cycle to the other. This generalizes the extensively studied uniquely Hamiltonian graphs. In this paper, we show that Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. To show this, we reduce Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition, which we believe is interesting in its own right. We complement our results by constructing infinite families of regular Hamiltonian-transitive graphs and take a look at the opposite extremal case by constructing a family with many different Hamiltonian cycles up to symmetry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_21337 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Symmetry classes of Hamiltonian cycles Baligacs, Julia Brenner, Sofia Lutz, Annette Volk, Lena Combinatorics Discrete Mathematics 05C60, 05C38, 05C76, 68R05, 68R10 We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs where, for every pair of Hamiltonian cycles, there is a graph automorphism mapping one cycle to the other. This generalizes the extensively studied uniquely Hamiltonian graphs. In this paper, we show that Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. To show this, we reduce Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition, which we believe is interesting in its own right. We complement our results by constructing infinite families of regular Hamiltonian-transitive graphs and take a look at the opposite extremal case by constructing a family with many different Hamiltonian cycles up to symmetry. |
| title | Symmetry classes of Hamiltonian cycles |
| topic | Combinatorics Discrete Mathematics 05C60, 05C38, 05C76, 68R05, 68R10 |
| url | https://arxiv.org/abs/2506.21337 |