2023/05/16 by Klavdija Kutnar, Kutnar, Klavdija, Dragan Marušič +3
Chemistry · Materials Science · Mathematics · #05C25 #20B25 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Nanocluster Synthesis and Applications #Synthesis and Reactivity of Heterocycles
paper · pdf · doi:10.48550/arxiv.2305.09465
openalex publication_date 2023/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph X with a Hamilton cycle C, the \em compression factor κ(X,C) of C is the order of the largest cyclic subgroup of Aut(C)\capAut(X), and the \em Hamilton compression κ(X) of X is the maximum of κ(X,C) where C runs over all Hamilton cycles in X. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor, Merino and Mütze in [``The Hamilton compression of highly symmetric graphs'', \em arXiv preprint arXiv: 2205.08126v1 (2022)] whether for every positive integer k there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to k. Since an infinite family of Cayley graphs with Hamilton compression equal to 1 was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products ℤp\rtimesℤk where p is a prime and k ≥ 2 a divisor of p-1. Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to 1 are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given.