Symmetry Classes of Hamiltonian Cycles

We consider the Hamiltonian cycle on the left of Figure 2 and show that it cannot be mapped to the one in the middle, which is obtained by exchanging the roles of $G$ and $H$. For this, we show that every automorphism of $G\mathrm{\square }H$ preserves the set of vertical edges and the set of horizontal edges, using that the graphs are relatively prime. The assertion then follows because the two cycles have a different number of vertical edges. $◀$

After dealing with relatively prime graphs, the next step towards a classification is to consider the Cartesian product of a prime graph with itself.

Note that vertices of $G^{\mathrm{\square }n}$ are $n$-tuples of vertices of $G$ and two vertices $u$ and $v$ are adjacent if and only if they only differ in one component $i$ and $\{u_i,v_i\}$ is an edge of $G$. Let $E_i$ be the set of edges $\{u,v\}$ of $G^{\mathrm{\square }n}$ where $u$ and $v$ differ in their $i$-th component. Then $E_1,\mathrm{\dots },E_n$ is a partition of the edges of $G^{\mathrm{\square }n}$. Since $G$ is prime, every automorphism of $G^{\mathrm{\square }n}$ permutes the sets $E_1,\mathrm{\dots },E_n$ ([16, Theorem 6.10]), i.e., if $e,e^{\prime }\in E_i$ and the automorphism maps $e$ to $E_j$, then $e^{\prime }$ is also mapped to $E_j$.

Let $k:=|G|$. First, we consider the case that $k\ge 4$. Our strategy is as follows: We inductively construct cycles $C_n$ and ${\widehat{C}}_n$ (for $n\ge 2$) that cannot be mapped to each other. For this, we also make use of the auxiliary statement that the constructed cycles fulfill $|E(C_n)\cap E_i|\ge 4$ and $|E({\widehat{C}}_n)\cap E_i|\ge 4$ for all $i\in \{1,\mathrm{\dots },n\}$, where by slight abuse of notation, $E_i$ is also w.r.t. $n$.

We start with the base case, i.e., $n=2$. For simplicity, we call the edges in $E_1$ and $E_2$ vertical and horizontal edges, respectively. Let $(g_1,\mathrm{\dots },g_k)$ be a Hamiltonian cycle of $G$. From this cycle, we can construct the two Hamiltonian cycles $C_2$ and ${\widehat{C}}_2$ of $G^{\mathrm{\square }2}$ depicted on the left and right of Figure 2. Note that the constructions slightly change depending on the parity of $|G|$, but the following arguments hold for both. For the sake of contradiction, assume there is an automorphism $\phi \in \mathrm{Aut}(G\mathrm{\square }G)$ mapping $C_2$ to ${\widehat{C}}_2$. Since every vertical edge in ${\widehat{C}}_2$ is preceded and followed by horizontal edges (here we use $k\ge 4$), but all horizontal edges in $C_2$ are either preceded or followed by another horizontal edge, $\phi$ cannot swap the sets $E_1$ and $E_2$, so it preserves each. But this leads to a contradiction because there are $k-1$ consecutive vertical edges in $C_2$, but not in ${\widehat{C}}_2$. Also, note that both cycles contain at least $2(k-1)\ge 4$ edges from $E_1$ and from $E_2$ so that this completes the base case.

For the induction step, let $n\ge 3$. Let $u,v$ and $w$ be three consecutive vertices of $C_{n-1}$. Let $C_n$ be the cycle obtained from $C_{n-1}$ using $u,v$, and $w$ as depicted in Figure 2. Note here that the vertical edges in Figure 2 are precisely the edges in $E_n$. Analogously, construct ${\widehat{C}}_n$ from ${\widehat{C}}_{n-1}$ and three consecutive vertices $\widehat{u},\widehat{v}$ and $\widehat{w}$ in ${\widehat{C}}_{n-1}$. Note that

Further, since $C_n$ contains $k$ copies of the cycle $C_{n-1}$ with two edges removed and, by the induction hypothesis, $C_{n-1}$ uses at least 4 edges from $E_i$, we have

for all $i\in \{1,\mathrm{\dots },n-1\}$. We obtain the equations (2) and (3) similarly for the cycle ${\widehat{C}}_n$. It remains to prove that the cycles cannot be mapped to each other. Assume there is an automorphism ${\phi }_n\in \mathrm{Aut}(G^{\mathrm{\square }n})$ mapping $C_n$ to ${\widehat{C}}_n$. Using (2) and (3), we obtain that  for all $i\ne n$, so that $\phi$ has to preserve the set $E_n$. Thus, ${\phi }_n$ is of the form $({\phi }_{n-1},\alpha )$ for some ${\phi }_{n-1}\in \mathrm{Aut}(G^{\mathrm{\square }n-1})$ and $\alpha \in \mathrm{Aut}(G)$. Note that both cycles $C_n$ and ${\widehat{C}}_n$ contain precisely one path of edges in $E_n$ of length $k-1$, so that $\phi$ maps one to the other, i.e., the path $((v,g_1),\mathrm{\dots },(v,g_k))$ in $C_n$ is mapped to the path $((\widehat{v},g_1),\mathrm{\dots },(\widehat{v},g_k))$ in ${\widehat{C}}_n$. Hence, $\alpha$ either maps $g_1$ to $g_1$ or, in case $\alpha$ reverses the order of the path, to $g_k$. In both cases, ${\phi }_{n-1}$ maps $C_{n-1}$ to ${\widehat{C}}_{n-1}$, which contradicts the induction hypothesis. Therefore, $C_n$ cannot be mapped to ${\widehat{C}}_n$ by an automorphism. This completes the proof of the Lemma in case $k\ge 4$.

The case $|G|=3$ can be proven by a similar analysis and is deferred to the full version. $◀$

Now Theorem 4 follows immediately by combining Lemma 5 and Lemma 6. In case a graph decomposes into a Cartesian product of Hamiltonian graphs, we can deduce the following characterization of Hamiltonian-transitive graphs.

We argue that every Hamiltonian cycle contains precisely two edges leading from one layer to the other and that these have to lie next to each other, i.e., that the cycle depicted in the middle of Figure 4 is the only Hamiltonian cycle up to symmetry. To prove this, note first that the number of edges leading from one layer to the other used by a Hamiltonian cycle is even and at least two. We then prove that every Hamiltonian cycle uses either two consecutive such edges or all of them. Since $k$ is odd, the latter is not possible. $◀$

In the next two lemmata, we argue that in all other cases (where $|G|\ge 5$), the Cartesian product $G\mathrm{\square }{K}_2$ is not in $\mathscr{H}$. The difficulty is that we cannot assume any non-adjacency between vertices of $G$. More precisely, we will only use that $C_k\mathrm{\square }{K}_2$ is a subgraph of $G\mathrm{\square }{K}_2$ and that $u_i$ is non-adjacent to $v_j$ if $i\ne j$. First, we settle the case when $|G|$ is even.

The key idea is to show that the Hamiltonian cycle on the left side in Figure 4 cannot be mapped to both, the cycle in the middle and the cycle on the right via a graph automorphism. For this, we use that the Hamiltonian cycle on the left has the property that every vertex is adjacent to precisely one of the two vertices at distance three in the cycle. $◀$

Next, we conisder the case where $|G|$ is odd but not a cycle. Note that we need a different strategy here because the cycle we used in Lemma 10 (left side of Figure 4) only exists when $|G|$ is even.

First, we show that, if $G\mathrm{\square }{K}_2\in \mathscr{H}$, then $G$ fulfills some symmetry conditions. Then, we consider the cycle depicted in Figure 4 and use the symmetry conditions to show that it cannot be mapped to the cycle in the middle of Figure 4. $◀$

The only case that is left to settle for Theorem 8 is when $|G|=4$. Note that there are only 3 Hamiltonian graphs on 4 vertices and checking these (either by hand or computation), we obtain that $G=C_4$ is the only case where $G\mathrm{\square }{K}_2\in \mathscr{H}$. Together with Lemmas 9, 10, and 11, this completes the proof of Theorem 8.

We first show that (3) implies (1). Clearly, we have $K_n,C_n\in \mathscr{H}$. To see that also $K_{m,m}\in \mathscr{H}$, let $A\bigsqcup B$ be the bipartition of $K_{m,m}$ and observe that every Hamiltonian cycle of $K_{m,m}$ alternately uses a vertex of $A$ and $B$. Since every combination of permutations of $A$ and $B$ is an automorphism of $K_{m,m}$, every Hamiltonian cycle can be mapped to every other Hamiltonian cycle by an automorphism of $K_{m,m}$.

For the remaining implications, let us first argue that we can assume $1\in S$: by assumption, there exists an element $x\in S$ of order $n$. Note that the group automorphism $\phi (kx):=k$ induces an isomorphism between $\mathrm{Cay}(\mathrm{\Gamma },S)$ and $\mathrm{Cay}(\mathrm{\Gamma },\phi (S))$, so we can assume w.l.o.g. that $x=1$.

Next, we show that (1) implies (2). Consider the Hamiltonian cycle $C=(0,1,\mathrm{\dots },n-1)$ of $G$. Since, $y\mapsto y+1$ defines an automorphism of $G$, the cycle $C$ can be rotated by 1 so that the Hamilton compression of $C$ is $n$. Since $G\in \mathscr{H}$, by Lemma 13 every cycle of $G$ has Hamilton compression $n$.

It remains to show that (2) implies (3). Thus from now on, we assume that every Hamiltonian cycle in $G$ has Hamilton compression $n$ and we aim to show that $G$ is isomorphic to $K_n$, $C_n$, or $K_{m,m}$. If $G\cong ̸C_n$, we have $k\in S$ for some . Then we consider the Hamiltonian cycle $C^{\prime }=(0,k,k+1,k+2,\mathrm{\dots },n-1,k-1,k-2,\mathrm{\dots },1)$ in $G$. Since $C^{\prime }$ has Hamilton compression $n$, rotating $C^{\prime }$ by any $y\in \mathbb{N}$ yields an automorphism of $G$. For every $y\in \{1,\mathrm{\dots },\min \{k-1,n-k-1\}\}$, this automorphism maps the edge $\{k-1,k\}$ to $\{k-1-y,k+y\}$. The existence of this edge implies $(k+y)-(k-1-y)=2y+1\in S$, which shows that $\{1,3,5,\mathrm{\dots },\min \{2k-1,2(n-k)-1\}\}\subseteq S$.

We have shown that, for every $k\in S$, we have $\{1,3,5,\mathrm{\dots },\min \{2k-1,2(n-k)-1\}\}\subseteq S$. Applying this repeatedly, we obtain that $S$ contains all odd numbers up to $n-1$. In particular, if $n$ is odd, we obtain that $S=\{1,\mathrm{\dots },n-1\}$ because $S$ is inverse-closed. This means that $G\cong K_n$.

Now assume that $n$ is even. In this case, we obtain that $A≔\{1,3,5,\mathrm{\dots },n-1\}\subseteq S$. If equality holds, we have $G\cong K_{m,m}$. Otherwise, $G$ is a supergraph of $K_{m,m}$ and $S$ contains an element $2l$ for some . We show that, for every $l^{\prime }\le \frac{n}{2}$, we also have $2l^{\prime }\in S$: Since $S$ contains all elements in $A$, note that every permutation of $(0,1,2,\mathrm{\dots },n-1)$, where every second element is in $A$, is a Hamiltonian cycle of $G$. Let $C^{\prime }$ be the Hamiltonian cycle obtained from $(0,\mathrm{\dots },n-1)$ by replacing $2l$ and $2l^{\prime }$. Rotating $C^{\prime }$ by $n-1$ (i.e., by 1 in the other direction) maps the edge $\{1,2l+1\}$ to $\{0,2l^{\prime }\}$, and hence, $2l^{\prime }\in S$. This shows that $S=\mathrm{\Gamma }\setminus \{0\}$, i.e., $G\cong K_n$. $◀$

The strategy is to show that, for every Hamiltonian cycle $C_K$ of $K$, we have $\kappa (C_K)=k$. By [14, Section 1.4], this implies that $K$ is the Cayley graph of a cyclic group and the generating set contains an element of order $k$. The assertion then follows from Theorem 17.

Fix a Hamiltonian cycle $C_K$ of $K$. To prove that $\kappa (C_K)=k$, we will make use of the following claim.

The proof of this claim is deferred to the full version and we argue here why it implies the Theorem. Since $G\in \mathscr{H}$, every Hamiltonian cycle of $G$, in particular $C$, is $\kappa (G)$-symmetric. Therefore, rotating $C$ by a multiple of $\alpha$ defines an automorphism of $G$. Together with Claim 22, this means that $C$ can be rotated by $\mu (C)$ (in counter-clockwise direction in Figure 5). This maps the first layer of $G$ bijectively to the last, inducing an automorphism of $K$. More precisely, $v_{0,j}$ is mapped to $v_{l-1,j+1modk}$. The induced automorphism of $K$ then maps $v_j$ to $v_{j+1modk}$, i.e., it rotates $C_K$ by 1. Therefore, $\kappa (C_K)=k$. $◀$

The key idea is to show that condition (2) in Theorem 21 is fulfilled, which then immediately implies the assertion, i.e., it is only left to prove that, for every prime number $p$ that divides $|G|$, $p$ also divides $\kappa (G)$. For this, we distinguish two cases on the prime factors of the order of elements in $S$. In one case, the assertion follows by Lemma 15. In the other case, we use Lemma 14 to decompose $\mathrm{\Gamma }$ into a direct product, Lemma 12 to decompose $G$ into a Cartesian product and Lemma 5 to deduce that one factor is trivial. $◀$

In the following two results, we build on Lemma 23 and further resolve the cases where $K$ is complete or a cycle.

First, we argue that, if two vertices of different layers are adjacent, then all vertices of the layers are adjacent. For this, we construct a suitable Hamiltonian cycle and rotate it using $\kappa (G)>1$. Second, we argue that every pair of layers has adjacent vertices by constructing structurally different Hamiltonian cycles if this is not the case. $◀$

For the sake of contradiction, assume that $K$ is a cycle. Since $\kappa (G)>1$, every Hamiltonian cycle has a non-trivial rotation. By suitably choosing the parameter $𝒂$ of the zigzag cycle (Definition 19), we obtain that this rotation maps two non-adjacent vertices in the first layer to two adjacent vertices in different layers, which is a contradiction. $◀$

The last step before concluding the main theorem is to settle the cases where $|K|$ or $l$ is small.

We distinguish three cases: either $S$ contains a generator; or all elements in $S$ have order 3; or there exists $s\in S$ with $|\mathrm{\Gamma }:⟨s⟩|=3$. In the first case, the assertion follows from Theorem 17. In the second case, $\mathrm{\Gamma }$ is a power of ${\mathbb{Z}}_3$ and we conclude with Lemma 16. In the last case, we show that $\kappa (G)$ is a multiple of three and rotating a suitable Hamiltonian cycle by $|G|/3$ yields a contradiction. $◀$

Now, we have all the tools at hand to prove Theorem 2.

First, assume that $\kappa (G)=1$. By [14, Theorem 6.4], this implies $S=\{s_{p_1},\mathrm{\dots },s_{p_r}\}$ for pairwise distinct prime numbers $p_1,\mathrm{\dots },p_r$ such that the element $s_{p_i}$ has order $p_i$ for $i=1,\mathrm{\dots },r$. By Lemmas 12 and 14, we obtain the Cartesian product decomposition $G=\mathrm{Cay}(⟨s_{p_1}⟩,\{s_{p_1}\})\mathrm{\square }\mathrm{\dots }\mathrm{\square }\mathrm{Cay}(⟨s_{p_r}⟩,\{s_{p_r}\})$. Theorem 4 then yields $r=1$, and thus $G=C_{p_1}$ is a cycle.

From now on, assume $\kappa (G)>1$. By Lemma 26, we obtain that $\mathrm{\Gamma }={\mathbb{Z}}_3^t$ for $t\ge 4$; or $G$ is complete; or a cycle; or there exists $s\in S$ of order at least $5$ and $|\mathrm{\Gamma }:⟨s⟩|\ge 5$. In the second and third cases, there is nothing to do. In the first case, we can choose $s_1,s_2\in S$ such that $\mathrm{\Delta }:=⟨S^{\prime }⟩:=⟨s_1,s_2⟩$ has order $9$ and $|\mathrm{\Gamma }:\mathrm{\Delta }|\ge 9$. Similarly, in the last case, we can set $S^{\prime }:=\{s\}$, so that $\mathrm{\Delta }=⟨S^{\prime }⟩$ has order at least 5 and index at least 5. Consider the $K$-$l$-layer structure given by $S^{\prime }$ as described at the beginning of this section. By Lemma 23, $K=\mathrm{Cay}(\mathrm{\Delta },S^{\prime })$ is a cycle or a complete graph. The first case is excluded by Lemma 25. In the second, $G$ is a complete graph by Lemma 24. $◀$

From Theorems 8 and 17, we already know that $C_n,C_4\mathrm{\square }{K}_2$, and $C_l\mathrm{\square }{K}_2$ for $l$ odd are in $\mathscr{H}$. For the other direction, assume $G\in \mathscr{H}$. Let $S^{\prime }≔S\setminus \{\pm s\}$ and $K≔\mathrm{Cay}(⟨S^{\prime }⟩,S^{\prime })$. The cases of $|K|=2$ and $|K|=3$ are dealt with separately. In case $|K|\ge 4$, the key idea is to use the group-induced $K$-$l$-layer structure and exploit that only edges corresponding to $s$ and $-s$ connect different layers. Then we consider the Hamiltonian cycles $C$ and $\widehat{C}$ of $G$ as depicted on the left and in the middle of Figure 6. Next, we show that every automorphism that maps $C$ to $\widehat{C}$ maps the green vertices $a,b,c$ and $d$ in $C$ to $V_2\cup V_{l-1}$ in $\widehat{C}$. Then we exploit the distance and order of the vertices $a,b,c$ and $d$ on the cycle $C$, as well as the fact that $a$ and $d$ are adjacent, to obtain a contradiction by doing several case distinctions. $◀$

In the next two lemmas, we settle the cases where $l\in \{2,3\}$.

We use that $G$ has a group-induced $K$-$l$-layer structure (for $l=2$, respectively $l=3$) to construct Hamiltonian cycles of $G$ from a Hamiltonian cycle of $K$. The key idea in both cases is to use that $\kappa (G)$ is even by Lemma 15. This means that every Hamiltonian cycle of $G$ can be rotated by $k:=|K|$ in the case $l=2$, and by $3k/2$ in the case $l=3$.

In the case $l=3$, we construct a Hamiltonian cycle of $G$ where this rotation leads to a contradiction. In the case $l=2$, by suitably choosing Hamiltonian cycles of $G$, the rotation by $k$ induces symmetries of $K$. In addition, we use that the case of Cartesian products is already settled in Theorem 8, so we can assume that $G$ consists of two copies of $K$ connected by two disjoint matchings. Using the second matching and the symmetries of $K$, we then construct Hamiltonian cycles of $G$ that cannot be mapped to each other by an automorphism. $◀$

Theorem 3 now follows immediately by combining Lemmas 27, 28, and 29.