Infinite families of vertex-transitive graphs with prescribed Hamilton compression

Abstract

Given a graph $X$ with a Hamilton cycle $C$, the {\em compression factor $\kappa (X,C)$ of $C$} is the order of the largest cyclic subgroup of $\mathrm{Aut}(C)\cap \mathrm{Aut}(X)$, and the {\em Hamilton compression $\kappa (X)$ of $X$ } is the maximum of $\kappa (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 ${\mathbb{Z}}_p⋊{\mathbb{Z}}_k$ where $p$ is a prime and $k\ge 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.

11 pages