2026-07-26T02:16:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24122 2025-11-12T13:33:19Z ddc:004 open_access

Symmetry Classes of Hamiltonian Cycles Baligács, Júlia Brenner, Sofia Lutz, Annette Volk, Lena Hamiltonian cycles graph automorphisms Cayley graphs abelian groups Cartesian product of 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Júlia Baligács and Sofia Brenner and Annette Lutz and Lena Volk 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.15 urn:nbn:de:0030-drops-241221 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode