Symmetry classes of Hamiltonian cycles
This work provides foundational results for a new symmetry-based classification of Hamiltonian cycles, relevant to graph theorists studying cycle structures and automorphisms.
The paper introduces the concept of Hamiltonian-transitive graphs, where all Hamiltonian cycles are equivalent under graph automorphisms, generalizing uniquely Hamiltonian graphs. It shows that Cayley graphs of abelian groups are not Hamiltonian-transitive under mild conditions, and constructs infinite families of Hamiltonian-transitive graphs.
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.