Hamiltonicity in generalized quasi-dihedral groups ^†^†thanks: Key Words: Cayley graphs, Hamiltonian double rays, Infinite graph, Infinite groups ^†^†thanks: Mathematics Subject Classification 2010: 05C25, 05C45, 05C63, 20E06, 20F05.

Babak Miraftab Konstantinos Stavropoulos

Abstract

Witte Morris showed in [21] that every connected Cayley graph of a finite (generalized) dihedral group has a Hamiltonian path. The infinite dihedral group is defined as the free product with amalgamation $\mathbb{Z}_{2}\ast\mathbb{Z}_{2}$ . We show that every connected Cayley graph of the infinite dihedral group has both a Hamiltonian double ray, and extend this result to all two-ended generalized quasi-dihedral groups.

1 Introduction

A Hamiltonian cycle(path) in a finite graph is a cycle(path) which includes every vertex of the graph. A graph $G$ is vertex-transitive if any two vertices $v_{1}$ and $v_{2}$ of $G$ , there is some automorphism $f\colon G\to G$ such that $f(v_{1})=v_{2}$ . The Lovász conjecture for vertex-transitive graphs states that every finite connected vertex-transitive graph contains a Hamiltonian cycle except five known counterexamples. Nevertheless, even the weaker version of the conjecture for finite Cayley graphs is still wide open. For a survey on the field, see [20, 11]. A dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Witte showed in [21] that every connected Cayley graph of a finite (generalized) dihedral group has a Hamiltonian path. It is worth mentioning that the existence of a Hamiltonian cycle in a dihedral group is still not known.

While all preceding results concerned finite graphs, Hamiltonian cycles (paths) have also been considered in infinite graphs. One can suggest the Hamiltonian ray as a generalisation to an infinite graph for the Hamiltonian path, however the correct infinite analogue of a Hamiltonian cycle is controversial. The first thing coming to mind is a spanning double-ray, an infinite connected graph in which each vertex has degree two, which we will refer to as a Hamiltonian double-ray.

It is an easy observation to see that the Lovász conjecture already fails for infinite Cayley graphs with Hamiltonian double-rays in place of Hamiltonian cycles, since the amalgamation of more than $k+1$ groups on a subgroup of order $k$ will produce groups with Cayley graphs that have separators of size $k$ whose removal leaves more than $k+1$ components, a well-known obstruction to Hamiltonicity (see [10]).

This obstruction practically ceases to exist for two-ended groups though. It was proven in [13, 16] that any Cayley graph of an abelian two-ended group contains a Hamiltonian double ray. In particular, the following has been conjectured.

Conjecture 1 ([12]).

Any Cayley graph of a group with at most two ends has a Hamiltonian double ray.

In this paper, we address the result of Witte [21] for infinite dihedral groups as well as dihedral groups and we make progress towards Conjecture 1. Our main result is the following

Theorem 1.1.

Let $G=\langle S\rangle$ be a two-ended generalized quasi-dihedral group. Then $\mathsf{Cay}(G,S)$ contains a Hamiltonian double ray.

The following Corollary is an immediate consequence of Theorem 1.1.

Corollary 1.2.

Every connected Cayley graph of the infinite dihedral group $\mathbb{Z}_{2}\ast\mathbb{Z}_{2}$ has a Hamiltonian double ray.

Our proof relies on extracting infinite two-ended grids or infinite two-ended cubic “cylindrical walls” (the precise definition of which we defer to Section 4) as spanning subgraphs of the Cayley graph. We prove that they, in turn, contain Hamiltonian double rays and circles.

2 Preliminaries

We start with the definition of generalized dihedral groups. The generalized dihedral group on an abelian subgroup $K=\langle S\mid R\rangle$ is the group $\mathsf{Dih}(K):=\langle S,b\mid R,b^{2},bkb^{-1}k,\forall k\in K\rangle$ . Alternatively, it is the external semidirect product $D(K)=K\rtimes_{\phi}\mathbb{Z}_{2}$ , where $K$ is abelian and $\phi(1)(g)=-g$ for any $g\in K$ , in additive notation. When $K=\mathbb{Z}$ , we obtain the infinite dihedral group $D_{\infty}$ . Note that an alternative presentation of $D_{\infty}$ is $\langle a,b\mid a^{2}=b^{2}\rangle=\mathbb{Z}_{2}\ast\mathbb{Z}_{2}$ . Next, we extend this definition to a more general setting.

Definition 1.

Let $G$ be a group with an abelian subgroup $K=\langle S\mid R\rangle$ of index $2$ . Then $G$ is called generalized quasi-dihedral (on $K$ and $b$ ) if $G$ has the presentation $\langle S,b\mid R,b^{n},bkb^{-1}k,\forall k\in K\rangle$ .

Clearly, every generalized dihedral group is generalized quasi-dihedral but not the other way around, as $\mathbb{Z}_{4}$ easily shows for example. Furthermore if $n=4$ , then our notation leads to generalized dicyclic groups.

Let $G_{1}=\langle S_{1}\mid R_{1}\rangle$ and $G_{2}=\langle S_{2}\mid R_{2}\rangle$ be two groups. Suppose that a subgroup $H_{1}$ of $G_{1}$ is isomorphic to a subgroup $H_{2}$ of $G_{2}$ , say an isomorphic map $\phi\colon H_{1}\to H_{2}$ . The free product with amalgamation of $G_{1}$ and $G_{2}$ over $H_{1}\cong H_{2}$ is

G_{1}\underset{H_{1}}{\ast}G_{2}=\langle S_{1}\cup S_{2}\mid R_{1}\cup R_{2}\cup h\phi(h)^{-1},\forall h\in H_{1}\rangle.

For more details and applications of free products with amalgamation, see [15].

Lemma 2.1.

[3, Theorem 11.3] Let $G_{1}$ and $G_{2}$ be two groups with isomorphic subgroups $H_{1}$ and $H_{2}$ respectively. Let $T_{i}$ be a left transversal¹¹1A transversal is a system of representatives of left cosets of $H_{i}$ in $G_{i}$ and we always assume that $1$ belongs to it. of $H_{i}$ for ${i=1,2}$ . Any element $x\in G_{1}\ast\!\!_{H}G_{2}$ can be uniquely written in the form $x=x_{0}x_{1}\cdots x_{n}$ with the following:

(i)

$x_{0}\in H_{1}$ .
(ii)

$x_{j}\in T_{1}\setminus 1$ or $x_{i}\in T_{2}\setminus 1$ for $j\geq 1$ and the consecutive terms $x_{j}$ and $x_{j+1}$ lie in distinct transversals.

A graph $\Gamma$ is called locally finite if every vertex has finite degree. A ray in a graph is a oneway infinite path, and an end of a locally finite graph is an equivalence class of rays under the relation $R_{1}\sim R_{2}$ if for every finite set of vertices $S$ , all but finitely many vertices of $R_{1}$ and $R_{2}$ lie on the same component of $\Gamma\setminus S$ .

Let $G$ be a finitely generated group. Let $S\subseteq G$ be a finite generating set of $G$ and let $\mathsf{Cay}(G,S)$ be the Cayley graph of $G$ with respect to $S$ . The number of ends of $G$ is defined as the number of ends of $\mathsf{Cay}(G,S)$ . A basic fact in the theory of ends for groups says that the number of ends of $G$ does not depend on the choice of a finite generating set $S$ of $G$ , so that it is well-defined, see Corollary 2.3 of [14]. We finish this section with the following theorem:

Theorem 2.2.

[14, Theorem 1.1] Let $G$ be a two-ended group with a finite normal subgroup $K$ . Then the following statements are equivalent:

(i)

$G=A\ast_{K}B$ .
(ii)

$G/K=D_{\infty}$ .

3 The structure of GQD groups

We start with the following lemma which is immediate by the definition of a generalized quasi-dihedral group.

Lemma 3.1.

Let $G$ be a generalized quasi-dihedral on $K$ and $b$ . Then the following statements hold:

(i)

$xkx^{-1}k=1$ , for every $x\in G\setminus K$ and $k\in K$ .
(ii)

If $x\in G\setminus K$ with finite order, then $G$ is generalized quasi-dihedral on $K$ and $x$ , and moreover $x^{4}=1$ .
(iii)

Every subgroup of $K$ is normal in $G$

Proof.

(i)

Let $x=kb\in Kb$ . Then $xk^{\prime}x^{-1}=kbk^{\prime}b^{-1}k^{-1}=kk^{\prime-1}k^{-1}=k^{\prime-1}$ .
(ii)

Since the order of $x$ is finite, the first part implies that $G$ is generalized quasi-dihedral on $K$ and $x$ . Moreover, for the element $x^{2}\in K$ we have by Definition 1 that $xx^{2}x^{-1}=x^{-2}$ , or equivalently $x^{4}=1$ .
(iii)

This part is a direct consequence of the first part.∎

By Lemma 3.1, we will say that $G$ is generalized quasi-dihedral just on $K$ when we don’t want to fix a specific generator $b$ with finite order outside of $K$ .

Lemma 3.2.

[21, Theorem 5.1] If a finite group $G$ has a subgroup $N$ of index 2 such that every subgroup of $N$ is normal in $G$ , then every Cayley graph of $G$ has a Hamiltonian path.

As a combination of Lemma 3.1 and Lemma 3.2 we obtain the following corollary.

Corollary 3.3.

Let $G$ be a finite generalized quasi-dihedral group. Then every Cayley graph of $G$ has a Hamiltonian path.∎

Our ultimate goal is to extend the above result to infinite generalized quasi-dihedral groups. But first we need to study some properties of infinite generalized quasi-dihedral groups.

We start with study of two-ended groups. The following result seems to be folklore, but unfortunately we could not find any reference for it, so we include a short proof for the sake of completeness.

Lemma 3.4.

Let $G=A\ast_{K}B$ be a $2$ -ended group. Then $K$ is normal in $G$ .

Proof.

Since the index of $K$ is $2$ in both $A$ and $B$ , we may assume the presentations $A=K\sqcup Kb$ and $B=K\sqcup Kb^{\prime}$ , where $b\in A\setminus B$ and $b^{\prime}\in B\setminus K$ . By the definition of the free product with amalgamation we know that $G$ has the following presentation:

\langle K,b,b^{\prime}\mid R_{1}\cup R_{2}\rangle,

where $A=\langle K,b\mid R_{1}\rangle$ and $B=\langle K,b^{\prime}\mid R_{2}\rangle$ . We note that the index of $K$ in $A$ and $B$ is two and so $K$ is normal in $A$ and $B$ . Therefore, $gkg^{-1}$ lies in $K$ for every $k\in K\cup\{b,b^{\prime}\}$ and thus also for every $g\in G$ . ∎

Lemma 3.5.

Let $G=A\ast_{K}B$ , where $A=K\sqcup Kb$ and $B=K\sqcup Kb^{\prime}$ . Then the following statements hold:

(i)

$G=K\langle b,b^{\prime}\rangle$
(ii)

$K(bb^{\prime})^{\ell}=K(b^{\prime}b)^{-\ell}$ for every $\ell\in\mathbb{Z}$ .
(iii)

$G=K\langle bb^{\prime}\rangle\langle b\rangle$ .
(iv)

$g\in G$ is torsion if and only if $g\in K$ or $g=k(bb^{\prime})^{n}b$ , where $k\in K$ and $n\in\mathbb{Z}$ .
(v)

$g\in G$ is not torsion if and only if $g=k(bb^{\prime})^{n}$ , where $k\in K$ and $n\in\mathbb{Z}^{*}$ .

Proof.

(i)

The first part follows from Lemma 2.1 that $G=K\langle b,b^{\prime}\rangle$ .
(ii)

We note that $b^{2}$ and $b^{\prime 2}$ both lie in $K$ . Hence we have $K=Kbb^{\prime}b^{\prime}b$ and so $K(b^{\prime}b)^{-1}=Kbb^{\prime}$ and a straightforward induction finishes this part.
(iii)

The second part with the help of Lemma 2.1 implies the third item.

Next we prove (iv) and (v) together. Assume that $g$ is an arbitrary element in $G$ . By the last part, we deduce that $Kg$ is either $K(bb^{\prime})^{n}b$ or $K(bb^{\prime})^{n}$ . We first let $Kg=K(bb^{\prime})^{n}b$ . Then we have

$\displaystyle Kg^{2}$	$\displaystyle=K(bb^{\prime})^{n}b(bb^{\prime})^{n}b$
	$\displaystyle=K(bb^{\prime})^{n}bb(b^{\prime}b)^{n-1}b^{\prime}b$
	$\displaystyle=K(bb^{\prime})^{n}(b^{\prime}b)^{n}$	(1)
	$\displaystyle=K(b^{\prime}b)^{-n}(b^{\prime}b)^{n}$	(2)
	$\displaystyle=K$

We note that we apply the second item on (1) in order to get (2). So we showed that $g^{2}$ lies in $K$ and so $g$ has finite order.

Next assume to contrary that $(k(bb^{\prime})^{n})^{\ell}=1$ , where $n\neq 0$ and so $(bb^{\prime})^{n\ell}\in K$ . Without loss of generality we assume that $n\ell$ is the smallest number with this property. By considering Lemma 2.1, we deduce that $[G:K]<\infty$ . Since $K$ is a finite subgroup, we infer that $G$ is finite and it yields a contradiction.∎

Lemma 3.6.

[18, 3.3.15] Let $G$ be a group with a subgroup $H$ of finite index. Then there exists a normal subgroup $N\leq H$ of $G$ such that $[G:N]<\infty$ .

For the remainder of the paper, when not stated otherwise $G$ will denote an infinite generalized quasi-dihedral group $G=A\ast_{K}B$ , where $A$ is generalized quasi-dihedral on $K$ and $b$ , $B$ is generalized quasi-dihedral on $K$ and $b^{\prime}$ , and $a=bb^{\prime}$ . As a result of Lemma 3.10, we see that for every $g=ka^{i}\in K\langle a\rangle$ we have $g^{b}=b(ka^{i})b^{-1}=k^{-1}a^{-i}=g^{-1}$ .

Pretty much the same computation shows that $s^{g}=gsg^{-1}=s^{-1}$ for every $g\notin K\langle a\rangle$ and generator $s\in S\cap K\langle a\rangle$ . We obtain the following.

Corollary 3.7.

Let $G=\langle S\rangle$ . If $S\cap K\langle a\rangle\neq\emptyset$ , then $\langle S\cap K\langle a\rangle\rangle\unlhd G$ . ∎

Lemma 3.8.

[17, Lemma 5.6] Let $H$ be a subgroup of finite index in $G$ . Then the number of ends of $H$ is the same as the number of ends of $G$ .

Theorem 3.9.

Let $G=A\ast_{K}B$ be a two-ended group. Then if $G$ is generalized quasi-dihedral, then $A$ and $B$ are generalized quasi-dihedral on $K$ .

Proof.

First we assume that $G$ is a generalized quasi-dihedral group on $H$ and $b$ and so $[G:H]=2$ . Since $G$ is generated by $H$ and $b$ and also the order of $b$ is finite, we infer that $[G:H]<\infty$ . It follows from Lemma 3.8 that $H$ is a two-ended abelian group. So $H$ must be isomorphic to $\langle a\rangle\oplus K$ , where $K=\langle X\mid Y\rangle$ is a finite abelian group. We note that $K$ is only a finite subgroup of $H$ and so it must be a characteristic subgroup of $H$ . On the other hand $H$ is a normal subgroup and we conclude that $K$ is a normal subgroup in $G$ , see Theorem 6.14 of [19]. We now have

	$\displaystyle G$	$\displaystyle\cong\langle a,b,X\mid Y,b^{n},axa^{-1}x^{-1},\forall x\in X,bhb^{-1}h,\forall h\in H\rangle$		(3)
	$\displaystyle\frac{G}{K}$	$\displaystyle\cong\langle a,b\mid K,b^{n},bab^{-1}a\rangle$		(4)

We know $b^{2}$ lies in $K$ and so $G/K\cong D_{\infty}$ . It follows from Theorem 2.2 that the group $G$ can written as $A\ast_{K}B$ , where $[A:K]=[B:K]=2$ .

Finally, we show that $A=aK\sqcup K$ is a generalized quasi-dihedral on $K$ . We note that $G=H\sqcup bH$ and so $a=bh$ for $h\in H$ . The rest follows from the relation $bhb^{-1}h=1$ . Similarly, one can show that $B$ is also generalized quasi-dihedral. ∎

Lemma 3.10.

Let $G=A\ast_{K}B$ be a generalized quasi-dihedral groups such that $A=K\sqcup bK$ and $B=K\cup b^{\prime}K$ . Then the following are true:

(i)

$G=K\langle a\rangle\langle b\rangle$
(ii)

$a\in C_{G}(K)$ .
(iii)

$ba^{m}=a^{-m}b$ and $\langle a\rangle\trianglelefteq G$ .
(iv)

$g^{2}=b^{2}$ for every $g\notin K\langle a\rangle$ .
(v)

$a^{-1}=b^{\prime}b.$

Proof.

It follows from Theorem 3.9 that $H=\langle a\rangle K$ , where $\langle a\rangle\cong\mathbb{Z}$ and $K$ is a finite abelian group. ∎

It is well-known that every subgroup of a finite dihedral group is either cyclic or dihedral. It is seeminlgy folklore that this property translates to the infinite dihedral group as well, but we couldn’t find a reference for it.

Theorem 3.11.

Let $G$ be a generalized quasi-dihedral group on $K$ and $b$ . Let $H$ be a subgroup of $G$ . Then $H$ either is abelian or generalized quasi-dihedral. In particular, every subgroup of infinite dihedral group is either cyclic or infinite dihedral.

Proof.

If $H$ is a subgroup of $K$ , then $H$ is abelian and we are done. Assume that $H\nsubseteq K$ , then $[H:H\cap K]=[G:K]=2$ . Since $G=K\sqcup Kb$ , one can see that there is a $k\in K$ such that $bk\in H$ and $H=(H\cap K)\sqcup(H\cap K)bk$ . Then for every $x\in K$ , we have that $(bk)x(bk)^{-1}=bkxk^{-1}b^{-1}=bxb^{-1}=x^{-1}$ . Next we have to show that the order of $bk$ is finite. Note that $(bk)^{2}=bkbk=bkk^{-1}b$ and so $(bk)^{2}=b^{2}$ . Since $G$ is a generalized quasi-dihedral group on $K$ and $b$ , we know that the order $b$ is finite. So $H$ is a generalized quasi-dihedral group on $H\cap K$ and $bk$ , as desired. ∎

3.1 Short cycles in Cayley graphs of two-ended generalized quasi-dihedral groups

In this subsection, we prove some crucial facts about $6$ - and $4$ -cycles in the Cayley graphs of two-ended generalized quasi-dihedral groups. Recall that $G=K\langle a\rangle\langle b\rangle$ by Corollary 3.5, where $a=bb^{\prime}$ .

Theorem 3.12.

Let $G=\langle S\rangle$ and let $s_{1},s_{2},s_{3}$ be three distinct elements in $G\setminus K\langle a\rangle$ . Then $s_{1}s_{2}s_{3}=s_{3}s_{2}s_{1}$ . If $s_{1},s_{2},s_{3}\in S\setminus K\langle a\rangle$ in particular, then for every $g\in G$ the sequence of vertices $g,gs_{1},gs_{1}s_{2},gs_{1}s_{2}s_{3},gs_{3}s_{2},gs_{3},g$ is a $6$ -cycle in $\mathsf{Cay}(G,S)$ .

Proof.

By Corollary 3.5, we know that that the elements of $G\setminus K\langle a\rangle$ are of the form $ka^{i}b$ . So, let $s_{1}=k_{\ell}a^{\ell}b$ , $s_{2}=k_{i}a^{i}b$ and $s_{3}=k_{j}a^{j}b$ . The following computation follows from Definition 1 and Lemma 3.10 and completes the proof:

$\displaystyle s_{1}s_{2}s_{3}=$	$\displaystyle(k_{\ell}a^{\ell}b)(k_{i}a^{i}b)(k_{j}a^{j}b)$
$\displaystyle=$	$\displaystyle(k_{\ell}a^{\ell}b)k_{i}a^{i}k_{j}^{-1}a^{-j}b^{2}$	(push the second $b$ to the right)
$\displaystyle=$	$\displaystyle k_{\ell}a^{\ell}bk_{j}^{-1}a^{-j}k_{i}a^{i}b^{2}$
$\displaystyle=$	$\displaystyle k_{j}a^{j}k_{\ell}a^{\ell}bk_{i}a^{i}b^{2}$	(push the first $b$ to the middle and $k_{j}a^{j}$ to the left)
$\displaystyle=$	$\displaystyle(k_{j}a^{j}b)k_{\ell}^{-1}a^{-\ell}k_{i}a^{i}b^{2}$
$\displaystyle=$	$\displaystyle s_{3}k_{i}a^{i}k_{\ell}^{-1}a^{-\ell}b^{2}$
$\displaystyle=$	$\displaystyle s_{3}k_{i}a^{i}bk_{\ell}a^{\ell}b$	(push a $b$ to the left)
$\displaystyle=$	$\displaystyle s_{3}s_{2}s_{1}.\hskip 253.22934pt\qed$

∎

Theorem 3.13.

Let $G=\langle S\rangle$ and let $s_{1}\in G\setminus K\langle a\rangle$ , $s_{2}\in K\langle a\rangle$ . Then, $s_{1}s_{2}=s_{1}^{-1}s_{2}$ . If $s_{1}\in S\setminus K\langle a\rangle$ , $s_{2}\in S\cap K\langle a\rangle$ in particular, then the sequence of vertices $g,gs_{1},gs_{1}s_{2},gs_{2},g$ is a $4$ -cycle in $\mathsf{Cay}(G,S)$ .

Proof.

It follows from Corollary 3.5 that $s_{1}=k_{i}a^{i}b$ and $s_{2}=k_{j}a^{j}$ . By Definition 1 and Lemma 3.10 we have:

s_{1}s_{2}=(k_{i}a^{i}b)(k_{j}a^{j})=k_{i}k_{j}a^{j}ba^{i}=k_{j}^{-1}a^{-j}k_{i}a^{i}b=s_{1}^{-1}s_{2}.\hskip 82.51282pt\qed

∎

4 Grids, Walls and Cylinders

As we already mentioned in the Introduction, the proof of Theorem 1.1 is based on extracting grids and cylindrical walls as spanning subgraphs. In this short section, we discuss the Hamiltonicity of the grid-like structures.

The Cartesian product $G\Box H$ of two graphs $G$ and $H$ is the graph with vertex set $V(G)\times V(H)$ , where vertices $(a,x)$ and $(b,y)$ are adjacent whenever $ab\in E(G)$ and $x=y$ , or $a=b$ and $xy\in E(H)$ .

Let $P_{k}$ denote the path graph on $k$ vertices and $D$ the double ray graph. The (two-ended) infinite grid $\mathcal{G}_{k}$ of height $k$ is the graph $P_{k}\Box D$ . The next lemma provides a way to extract a spanning grid and, consequently, a Hamiltonian double ray from a graph.

Lemma 4.1.

[12, Lemma 3.9] Let $G,H$ be two-ended locally finite graphs and let $G_{1},\ldots,G_{n}$ be disjoint subgraphs of $G$ such that

(i)

$\bigsqcup_{i=1}^{n}V(G_{i})=V(G)$ , and
(ii)

every $G_{i}$ contains a spanning subgraph $H_{i}$ , which is isomorphic to $H$ by means of an isomorphism $\phi_{i}:H\rightarrow H_{i}$ , and
(iii)

for every ${i<n}$ and every ${v\in H_{i}}$ there is an edge between $v$ and ${\phi_{i+1}\circ\phi^{-1}_{i}(v)}$ .

Let $R$ be a spanning double ray of $H$ . Then $G$ contains a spanning infinite grid of height $n$ . In particular, it contains a Hamiltonian double ray and a Hamiltonian circle.

The wall graph $W_{k}$ of height $k$ is the graph with vertex set $V(W_{k})=\mathbb{Z}\times\mathbb{Z}_{k}$ and edge set $E(W_{k})=E_{1}\cup E_{2}\cup E_{3}$ , where

	$\displaystyle E_{1}$	$\displaystyle=\{\{(n,m),(n+1,m)\}\mid n\in\mathbb{Z},m=0,\ldots,k-1\},$
	$\displaystyle E_{2}$	$\displaystyle=\{\{(2n,m),(2n,m+1)\}\mid n\in\mathbb{Z},m\equiv 0\ (\rm{mod}2)\},$
	$\displaystyle E_{3}$	$\displaystyle=\{\{(2n+1,m),(2n+1,m+1)\}\mid n\in\mathbb{Z},m\equiv 1\ (\rm{mod}2)\}.$

For $k+l$ even, the twisted cubic cylinder $\overline{W}_{k,l}$ of height $k$ and twist $l\in\mathbb{Z}$ is the graph with vertex set $V(\overline{W}_{k,l})=V(W_{k})=\mathbb{Z}\times\mathbb{Z}_{k}$ and edge set $E(\overline{W}_{k,l})=E(W_{k})\cup E^{\prime}_{l}$ , where

•

$E^{\prime}_{l}=\{\{(2n+1,k-1),(2n+1+l,0)\}\mid n\in\mathbb{Z}\}$ , when $k$ is even,
•

$E^{\prime}_{l}=\{\{(2n,k-1),(2n+l,0)\}\mid n\in\mathbb{Z}\}$ , when $k$ is odd.

The edges in $E_{2}\cup E_{3}$ are called straight and the edges in $E^{\prime}_{l}$ are called twisted. The $m$ -th row $R_{m}$ of $W_{k}$ and $\overline{W}_{k,l}$ is the double ray induced by $\mathbb{Z}\times\{m\}$ . For $j\geq 1$ , the $i$ -th block $B_{i,2j}$ of length $2j$ of $\overline{W}_{k,l}$ is the graph induced by the vertices

•

$(2i+1+n,m)$ , $n=0,\ldots,2j-1$ , $m\in\mathbb{Z}_{k}$ , when $k$ is even. The $i$ -th snake $S_{i,2j}$ of length $2j$ is then the unique Hamiltonian path from $(2i+1,0)$ to $(2i+1,k-1)$ in $B_{i,2j}$ .
•

$(2i+1-n,m)$ , $n=0,\ldots,2j-1$ , $m\in\mathbb{Z}_{k}$ , when $k$ is odd. The $i$ -th snake $S_{i,2j}$ of length $2j$ is then the unique Hamiltonian path from $(2i+1,0)$ to $(2i+2-2j,k-1)$ in $B_{i,2j}$ .

In particular, the $i$ -th column $Q_{i}$ of $\overline{W}_{k,l}$ is the path $S_{i,2}$ . The $i$ -th staircase $\Gamma_{i}$ of $\overline{W}_{k,l}$ is the unique path of length $2k-1$ from $(2i+1,0)$ to $(2i+1+k,k-1)$ .

Figure 1: A column in the twisted cubic cylinder

\overline{W}_{4,4}

The following lemma captures a surprising property of twisted cylinders: stretching a given twisted cylinder along carefully chosen double rays can transform it into a twisted cylinder with different parameters (see Fig. 2).

Lemma 4.2.

For any $k\geq 2$ and $l\in\mathbb{N}$ with $k+l$ even, the twisted cylinders $\overline{W}_{k,l}$ and $\overline{W}_{\frac{k+l}{2},\frac{3k-l}{2}}$ are isomorphic.

Proof.

For $r=0,\ldots,\frac{k+l}{2}-1$ , let $D_{r}$ be the double ray obtained by the concatenation of the all staircases $\Gamma_{i\frac{k+l}{2}+r}$ along twisted edges. We observe that $\overline{W}_{k,l}$ is isomorphic to $\overline{W}_{\frac{k+l}{2},\frac{3k-l}{2}}$ with rows $D_{0},\ldots,D_{\frac{k+l}{2}-1}$ . ∎

Figure 2: The double rays of

\overline{W}_{4,2}

that serve as rows of

\overline{W}_{3,5}

. The red snake edges correspond to twisted edges between the first(blue) and last(green) double ray of

\overline{W}_{3,5}

Lemma 4.3.

For any $k\geq 2$ and $l\in\mathbb{N}$ with $k+l$ even, the twisted cubic cylinder $\overline{W}_{k,l}$ contains a Hamiltonian double ray.

Proof.

If $k$ and $l$ are even $\geq 2$ , we obtain a Hamiltonian double ray by concatenating all snakes $S_{il,l}$ , $i\in\mathbb{Z}$ along twisted edges.

If $k$ and $l$ are odd $\geq 3$ , let $l_{1},l_{2}$ be positive even numbers such that $l_{1}+l_{2}=l+1$ . We then obtain a Hamiltonian double ray by concatenating all snakes $S_{il,l_{1}}$ and $S_{il-l_{1},l_{2}}$ , $i\in\mathbb{Z}$ in an alternating fashion along twisted edges.

It remains to check the cases when $l=0$ (and $k$ necessarily even) or $l=1$ (and $k$ odd). For $r=0,\ldots,k+l-1$ , let $D_{r}$ be the double ray obtained by the concatenation of the all staircases $\Gamma_{i\frac{k+l}{2}+r}$ along twisted edges. We conclude the proof by invoking Lemma 4.2 and noticing that $\frac{3k-l}{2}\geq 2$ . ∎

Lemma 4.4.

For any $k\geq 2$ and $l\in\mathbb{N}$ , the twisted cubic cylinder $\overline{W}_{k,l}$ contains a disjoint union of two double-rays which together span $\overline{W}_{k,l}$ .

Proof.

We can assume that $k\geq 3$ , as otherwise the result is trivial for $k=2$ . Moreover, we reduce the cases where $l=0,1,2,3$ to the next (general) cases by invoking Lemma 4.2.

If $k$ and $l$ are even $\geq 4$ , let $l_{1},l_{2}$ be positive even integers such that $l_{1}+l_{2}=l$ . We let $D_{1}$ be the double ray obtained by the concatenation of all snakes $S_{il,l_{1}}$ and $D_{2}$ the double ray obtained by the concatenation of all snakes $S_{il+l_{1}+1,l_{2}}$ , $i\in\mathbb{Z}$ along twisted edges as the two disjoint double rays that span a Hamiltonian circle of $\overline{W}_{k,l}$ .

If $k$ and $l$ are odd $\geq 5$ , let $l_{1},l_{2},l_{3}$ be positive even numbers such that $l_{1}+l_{2}+l_{3}=l+1$ . As before, we define the double ray $D_{1}$ as the concatenation of all snakes $S_{il,l_{1}}$ and $S_{il-l_{1},l_{2}}$ , $i\in\mathbb{Z}$ in an alternating fashion along twisted edges and $D_{2}$ as the concatenation of all $S_{il-l_{1}-l_{2},l_{3}}$ , $i\in\mathbb{Z}$ . The double rays $D_{1}$ and $D_{2}$ are then disjoint and span a Hamiltonian circle. ∎

5 Proof of the main Theorem

Let us quickly remind the following basic fact.

Lemma 5.1.

(Modular law)[18, 1.6.15] If $G$ is a group, $H$ is a subset of $L\leq G$ , and $K$ is a subset of $G$ , then $L\cap(HK)=H(L\cap K)$ .

Lemma 5.2.

Let $G=\langle S\rangle$ be an arbitrary group (not necessarily finite) with a subgroup $H$ of index $2$ . Then if $S\cap H=\emptyset$ , then $sS$ generates $H$ , where $s\in S$ .

Proof.

Let $h\in H$ be an arbitrary element of $H$ . Then $h=x_{1}\cdots x_{t}$ , where each $x_{i}\in S$ for $i=1,\ldots,t$ . We note that $t$ must be even in order for $h$ to lie in $H$ . This proves that $S^{2}$ generates $H$ . Finally, we show that every element $s_{i}s_{j}$ of $S^{2}$ can be generated by $sS$ by noting that $s_{i}s_{j}=s_{i}s^{-1}ss_{j}$ and $ss_{i}^{-1}\in sS$ . This completes the proof. ∎

We are ready to prove our main result. We will extensively use Definition 1 and Lemma 3.10 for the calculations throughout the proof, so we will mostly not specifically refer to them each time we use them.

Proof of Theorem 1.1.

Let $G=A\ast_{K}B=\langle S\rangle$ with $A=K\sqcup Kb$ , $B=K\sqcup Kb^{\prime}$ and $a=bb^{\prime}$ . We apply induction on the number of generators in $S$ . For the base case that $|S|=2$ , we immediately see that $\mathsf{Cay}(G,S)$ is a double ray (and it is straightforward to show that $G\cong D_{\infty}$ ). We split the proof of the induction step into two cases.

Case I . We first assume that $S\cap K\langle a\rangle=\emptyset$ . Let $s\in S$ and define $H:=\langle S^{\prime}\rangle$ , where $S^{\prime}:=S\setminus\{s,s^{-1}\}$ . We claim that

there is always an

s\in S

such that

H

is infinite.

(5)

Suppose not; by Lemma 3.5 every generator in $S^{\prime}$ has the form $ka^{i}b$ and let $s_{1}=k_{1}a^{i}b,s_{2}=k_{2}a^{j}b\in S^{\prime}$ . Notice that the element $s_{1}s_{2}=k_{1}k_{2}^{-1}b^{2}a^{i-j}\in H\cap K\langle a\rangle$ has finite order. By Lemma 3.5 we conclude that $i=j$ . Otherwise $s_{1}s_{2}$ is not torsion. Since $S^{\prime}\cup\{s,s^{-1}\}$ generates $G$ , we infer that $s=k^{\prime}a^{j}b$ , where $j\neq i$ . Therefore, the group $H^{\prime}:=\langle S\setminus\{s_{1},s_{1}^{-1}\}\rangle$ is infinite, as $ss_{1}$ is not torsion. So the claim is proved.

Thus, we can always assume that $H$ is infinite. In particular, we have $H/(H\cap K)\cong HK/K\leq G/K\cong D_{\infty}$ and so $H/(H\cap K)\cong D_{\infty}$ . We infer that $H=(H\cap K)\langle k_{\ell}a^{\ell},t\rangle$ , where $t\in S^{\prime}$ and for some $k_{\ell}a^{\ell}\in H$ , as $G$ is not commutative. In particular $H\cap K$ is a normal in $H$

We now state the following calculation, some steps of which we explain afterwards:

$\displaystyle K\langle a\rangle=$	$\displaystyle\langle S^{\prime},s\rangle\cap K\langle a\rangle$
$\displaystyle=$	$\displaystyle\langle H,s\rangle\cap K\langle a\rangle$
$\displaystyle=$	$\displaystyle\langle(H\cap K)\langle k_{\ell}a^{\ell},t\rangle,s\rangle\cap K\langle a\rangle$
$\displaystyle=$	$\displaystyle\left((H\cap K)\langle k_{\ell}a^{\ell}\rangle\langle t,s\rangle\right)\cap K\langle a\rangle$	(6)
$\displaystyle=$	$\displaystyle\left((H\cap K)\langle k_{\ell}a^{\ell}\rangle\right)\left(\langle t,s\rangle\cap K\langle a\rangle\right)$	(by Lemma 5.1)
$\displaystyle=$	$\displaystyle\left((H\cap K)\langle k_{\ell}a^{\ell}\rangle\right)\langle ts\rangle$	(7)

Let $s=k_{i}a^{i}b$ and $t=k_{j}a^{j}b$ . For (6), we first note that $(H\cap K)s=s(H\cap K)$ . Because assume that $k\in H\cap K$ and so $ks=kk_{i}a^{i}b=k_{i}a^{i}bk^{-1}=sk^{-1}$ . In addition, we have

(k_{\ell}a^{\ell})s=k_{\ell}a^{\ell}k_{i}a^{i}b=k_{i}a^{i}k_{\ell}a^{\ell}b=k_{i}a^{i}bk_{\ell}^{-1}a^{-\ell}=s(k_{\ell}a^{\ell})^{-1},

So $s$ commutes with $H\cap K$ and $k_{\ell}a^{\ell}$ and similarly one can show that $t$ commutes with $H\cap K$ and $k_{\ell}a^{\ell}$ as well. So $(H\cap K)\langle k_{\ell}a^{\ell}\rangle\langle t,s\rangle$ is a subgroup of $G$ .

Let $H^{\prime}:=(H\cap K)\langle k_{\ell}a^{\ell}\rangle$ . We have proven so far that $K\langle a\rangle=H^{\prime}\left(\langle t,s\rangle\cap K\langle a\rangle\right)$ , so it remains to show (7) which means that $\langle t,s\rangle\cap K\langle a\rangle=\langle ts\rangle$ .
It is not hard to see that $\langle t,s\rangle K\langle a\rangle=G$ . One can see that $G=K\langle a\rangle\sqcup K\langle a\rangle s$ and so $[G:K\langle a\rangle]=2$ implies that $[\langle t,s\rangle:\langle t,s\rangle\cap K\langle a\rangle]=2$ . We can now apply Lemma 5.2 and infer that $\{ts,ts^{-1},t^{2}\}$ generates $\langle t,s\rangle\cap K\langle a\rangle$ . On the other hand, we know that $H/(H\cap K)\cong D_{\infty}$ and so $t^{2}\in H\cap K$ . We claim that

H^{\prime}(ts)^{\ell}ts^{-1}

and

H^{\prime}(ts)^{\ell}t^{2}

can be expressed as

H^{\prime}(ts)^{\ell^{\prime}}

, where

\ell,\ell^{\prime}\in\mathbb{Z}

(8)

Observe that $ts=ts^{-1}s^{2}=ts^{-1}b^{2}=ts^{-1}t^{2}$ . Moreover, notice that that $t^{2}$ , $ts$ and $ts^{-1}$ lie in $K\langle a\rangle$ , hence they pairwise commute. Since $t^{2}\in H\cap K\subseteq H^{\prime}$ , we deduce that

H^{\prime}(ts)^{\ell}t^{2}=H^{\prime}t^{2}(ts)^{\ell}=H^{\prime}(ts)^{\ell}

and

H^{\prime}(ts)^{\ell}ts^{-1}=H^{\prime}t^{2}(ts)^{\ell}ts^{-1}=H^{\prime}(ts)^{\ell}ts^{-1}t^{2}=H^{\prime}(ts)^{\ell+1}.

So the claim is proved. Hence, we have shown that every coset of $H^{\prime}$ in $K\langle a\rangle$ is of the form $H^{\prime}(ts)^{\ell}$ . Observe that $H^{\prime}$ has finite index in $K\langle a\rangle$ , therefore we have

K\langle a\rangle=H^{\prime}\sqcup H^{\prime}(ts)\sqcup\cdots\sqcup H^{\prime}(ts)^{m}.

Recall that $G=K\langle a\rangle\sqcup K\langle a\rangle s$ . Therefore, the cosets of $H^{\prime}$ partition $G$ as follows:

	$\displaystyle G=$	$\displaystyle H^{\prime}\sqcup H^{\prime}(ts)\sqcup\cdots\sqcup H^{\prime}(ts)^{m}\sqcup$		(9)
		$\displaystyle\phantom{{}=1}H^{\prime}t\sqcup H^{\prime}(ts)t\sqcup\cdots\sqcup H^{\prime}(ts)^{m}t.$

We need a final observation. It is an easy induction on $\ell$ to see that for every $1\leq\ell\leq m$ and $t_{1},\ldots,t_{\ell}\in S^{\prime}$ (not necessarily distinct) we have that

	$\displaystyle H^{\prime}(t_{1}s)(t_{2}s)\ldots(t_{\ell}s)=$	$\displaystyle H^{\prime}(ts)^{\ell},$		(10)
	$\displaystyle H^{\prime}(t_{1}s)(t_{2}s)\ldots(t_{\ell-1}s)t_{\ell}=$	$\displaystyle H^{\prime}(ts)^{\ell-1}t.$		(11)

We are ready to extract a spanning twisted cubic cylinder from $\mathsf{Cay}(G,S)$ . Recall that $H=H^{\prime}\cup H^{\prime}t$ has a spanning double ray $R_{0}$ , which must necessarily alternate between the two cosets of $H^{\prime}$ in $H$ by the fact that $S^{\prime}\subseteq H^{\prime}t$ . Split $R$ into subpaths of length two between vertices of $H^{\prime}t$ and let $P=\{g,gt_{1},gt_{1}t_{2}\}$ be an arbitrary such subpath, where $g\in H^{\prime}t$ . By Theorem 3.12, there is a $6$ -cycle $C=\{g,gt_{1},gt_{1}t_{2},gt_{1}s_{2}s,gst_{2},gs\}$ . In other words, $C$ is obtained by connecting the ends of $P$ and $P^{\prime}=\{gst_{1}t_{2},gst_{2},gs\}$ with two edges labeled with $s$ . Clearly, $gt_{1}t_{2}s,gs\in H^{\prime}t$ and by (11) we have that $gst_{2}\in H^{\prime}tst$ . It follows that the concatenation of all such paths $P^{\prime}$ of length two gives rise to a spanning double ray $R_{1}$ of $H^{\prime}ts\cup H^{\prime}tst$ alternating between vertices of $H^{\prime}ts$ and $H^{\prime}tst$ , where the vertices of $H^{\prime}t$ in $R_{1}$ are connected by an $s$ -edge to the vertices of $H^{\prime}ts$ in $R_{2}$ .

Using exactly the same method, we obtain inductively for every $\ell\in\mathbb{Z}_{m+1}$ that $H^{\prime}(ts)^{\ell}\cup H^{\prime}(ts)^{\ell}t$ has a spanning double ray $R_{\ell}$ alternating between $H^{\prime}(ts)^{\ell}$ and $H^{\prime}(ts)^{\ell}t$ , where the vertices of $H^{\prime}(ts)^{\ell}t$ in $R_{\ell}$ are connected by an $s$ -edge to the vertices of $H^{\prime}(ts)^{\ell+1}$ in $R_{\ell+1}$ . This gives rise to a twisted cubic cylinder with rows $R_{0},R_{1},\ldots,R_{m}$ to conclude by Lemma 4.3 and Lemma 4.4 that $\mathsf{Cay}(G,S)$ contains a Hamiltonian double ray.

Case II .

Suppose that $S\cap K\langle a\rangle\neq\emptyset$ . Let $S_{1}:=S\setminus K\langle a\rangle$ (notice that $S_{1}\neq\emptyset$ ) and $S_{2}:=S\setminus S_{1}$ . Let $H^{\prime}$ be the subgroup generated by $S_{2}$ .
Subcase i: If $H^{\prime}$ is finite, then $H^{\prime}\subseteq K$ . Let $x\in S_{1}$ and $k\in K$ . By Theorem 3.13, we have $xk=k^{-1}x$ and also $kx=xk^{-1}$ . We note that $G/H^{\prime}\cong A/H^{\prime}\ast_{K/H^{\prime}}B/H^{\prime}$ and so $G/H^{\prime}$ is generalized quasi-dihedral. By the induction hypothesis the Cayley graph of $G/H^{\prime}$ with respect with $S_{1}H^{\prime}$ has a Hamiltonian double ray $\mathcal{R}$

\ldots,H^{\prime}x_{-2},H^{\prime}x_{-1},H^{\prime},H^{\prime}x_{1},H^{\prime}x_{2},\ldots,

where $x_{i}\in S_{1}$ for each $i\in\mathbb{Z}\setminus\{0\}$ . On the other hand, $\mathsf{Cay}(H,S_{2})$ has a Hamiltonian path. Since we showed that $xk=k^{-1}x$ and $kx=xk^{-1}$ , we invoke Lemma 4.1 and conclude that $G$ has a Hamiltonian double ray.
Subcase ii: If $H^{\prime}$ is infinite, then $[G:H^{\prime}]$ is finite. We note that $H^{\prime}$ is an abelian group and so it follows from [16, Theorem 1] that $\mathsf{Cay}(H^{\prime},S_{2})$ contains a Hamiltonian double ray $R$ . By Corollary 3.7 we know that $H^{\prime}$ is normal and moreover $S_{1}H^{\prime}$ generates the quotient $G/H^{\prime}$ . On the other hand, we know by Lemma 3.10 that $\langle KH^{\prime},aH^{\prime}\rangle=\langle K,a\rangle/H^{\prime}=K\langle a\rangle/H^{\prime}$ is an abelian subgroup of $G/H^{\prime}$ . Furthermore, we have that $[G/H^{\prime}:K\langle a\rangle/H^{\prime}]=[G:K\langle a\rangle]=2$ .

Since $bH^{\prime}gH^{\prime}=g^{-1}H^{\prime}bH^{\prime}$ for every $g\in K\langle a\rangle/H^{\prime}$ and $[G:H^{\prime}]$ is finite, we deduce that the quotient $G/H^{\prime}$ is a generalized quasi-dihedral group on $K\langle a\rangle/H^{\prime}$ and $bH^{\prime}$ .

It follows from Corollary 3.3 that $\mathsf{Cay}(G/H^{\prime},S_{1}H^{\prime})$ has a Hamiltonian path

g_{1}H^{\prime}=H^{\prime},g_{2}H^{\prime},\ldots,g_{n}H^{\prime}.

Observe that $g_{i}H^{\prime}$ contains a Hamiltonian double ray $g_{i}R$ for every $1\leq i\leq n$ in $\mathsf{Cay}(G,S)$ . Moreover, the vertices of $g_{i}R$ are connected to the vertices of $g_{i+1}R=(g_{i}R)s_{i}$ with a perfect matching whose edges are labeled with the same generator $s_{i}\in S_{1}$ . In combination with Lemma 3.13, this implies that conditions (ii) and (iii) of Lemma 4.1 hold and we are done. ∎

6 Final Remarks

In the final chapter, we illustrate different approaches to continue the study of Hamiltonicity of generalized quasi-dihedral groups.

6.1 Hamiltonian circles

While there have been many attempts to extend the definition of hamiltonian cycles for infinite graphs, there is no single method that generalizes all theorems of finite Hamiltonicity to locally finite graphs.

Here we follow the topolgical approach introduced in [6, 7, 8]. More specifically, the infinite cycles of a graph $G$ are defined as the circles(homeomorphic image of $S^{1}$ ) in the Freudenthal compactification $|G|$ , where $|G|$ denotes the graph $G$ endowed by $1$ -complex topology. A homeomorphic image of $[0,1]$ in $|G|$ is an arc in $G$ . A circle in $|G|$ is a Hamiltonian circle if it contains all vertices of $G$ . When $G$ is two-ended, there is a nice combinatorial description for Hamiltonian circles, see the following lemma.

Lemma 6.1.

[7, Theorem 2.5] If $\Gamma$ is a locally finite, two-ended graph and $C$ is a disjoint union of two double-rays which together span $\Gamma$ , each of which contains a ray to both ends of the graph, then $C$ is a Hamiltonian circle.∎

By the proof of Theorem 1.1 and Lemma 4.1 as well as Lemma 4.4, we have the following corollary.

Corollary 6.2.

Let $G=\langle S\rangle$ be a two-ended generalized quasi-dihedral group. If $\mathsf{Cay}(G,S)$ has degree at least three, it contains a Hamiltonian circle.

We believe that the same statements of Hamiltonicity go through when $G$ is a one-ended generalized quasi-dihedral group, too. We note that in that case the subrgroup $H$ of $G$ of index $2$ is an abelian one-ended group, hence $H$ is isomorphic to $\mathbb{Z}^{k}$ for some $k\geq 2$ .

Conjecture 2.

Let $G=\langle S\rangle$ be a one-ended generalized quasi-dihedral group. Then $\mathsf{Cay}(G,S)$ contains a Hamiltonian double ray(Hamiltonian circle).

6.2 Hamilton-connectivity

A finite graph is called Hamilton-connected if there is a Hamiltonian path between any pair of vertices of the graph. A finite bipartite graph is called Hamilton-laceable if there is Hamiltonian path between pair of vertices at odd distance. It is an easy observation that Hamilton-laceability (and not -connectivity) is the most that one can hope for in the case of finite bipartite graphs. The most celebrated theorem relating Cayley graphs and Hamilton-connectivity is due to Chen and Quimpo [4], who proved something stronger about the Hamiltonicity of Cayley graphs of finite abelian groups with degree at least three; they are actually Hamilton-connected, unless they are bipartite when they are Hamilton-laceable.

Alspach et al. prove in [1] extended this for Cayley graphs of finite generalized dihedral groups with degree at least three. Their proof also relies on extracting spanning finite versions of infinite two-ended grids or twisted cubic cylinders —defined as honeycomb toroidal graphs in [1]—, where the double rays of the rows are replaced with finite cycles. A large part of their paper revolves around proving that these finite graphs are Hamilton-connected or -laceable.

Notice that from the definition of Hamiltonian connectivity we immediately obtain a Hamiltonian cycle when the two endvertices are connected with an edge. Using this, let us generalize the notion of Hamilton-connectivity to the infinite setting. We say an infinite (bipartite) graph is Hamiltonian ray-connected (-laceable) if for any pair of vertices $u,v$ (at odd distance) there are two disjoint rays starting from $u,v$ spanning all the vertices of the graph. Similarly, an infinite (bipartite) graph is Hamiltonian arc-connected (-laceable) if for any pair of vertices $u,v$ (at odd distance) there are two rays starting from $u,v$ and a double ray, all pairwise disjoint, whose union spans all the vertices of the graph. Observe that when $u$ and $v$ are connected with an edge in both definitions, we directly obtain a Hamiltonian double ray and a Hamiltonian circle, respectively.

The fact that bipartite graphs can only be Hamilton-laceable fails for infinite graphs. It is very easy (but a bit tedious as well) to prove that two-ended infinite grids are not just Hamilton-laceable, but Hamilton-connected.

Problem 1.

Is $\mathsf{Cay}$ (G,S) both Hamiltonian ray- and arc-connected, where $G$ is a generalized quasi-dihedral group?

6.3 Decomposition and Uniqueness

Alspach, in [2, Unsolved Problem 4.5, p. 454]] conjectured the following. Let $G$ be an Abelian group with a symmetric generating set $S$ . If the Cayley graph $\mathsf{Cay}(G,S)$ has no loops, then it can be decomposed into Hamiltonian cycles (plus a $1$ -factor if the valency is odd) and see [5], for a directed version of this problem, Erde and Lehner [9] showed every 4-regular Cayley graph of an infinite abelian group all of whose finite cuts are even can be decomposed into Hamiltonian double rays, and so characterised when such decompositions exist. It raises the following question.

Problem 2.

Can every $4$ -regular Cayley graph of two-ended generalized quasi-dihedral group be decomposed into two hamiltonian double-rays(Hamiltonian circle)?

Finally, consider $D_{\infty}=\langle a,b\mid b^{2}=(ba)^{2}\rangle$ . The Cayley graph of $D_{\infty}$ with respect to $S=\{ba,b,ab\}$ contains a unique Hamiltonian circle. Naturally, we ask the following question.

Problem 3.

Let $G$ be a generalized quasi-dihedral group. For which generating $S$ of $G$ does $\mathsf{Cay}(G,S)$ contain a unique Hamiltonian circle?

References

[1] Brian Alspach, Chuan Chong Chen, and Matthew Dean. Hamilton paths in Cayley graphs on generalized dihedral groups. Ars Math. Contemp., 3(1):29–47, 2010. https://doi.org/10.26493/1855-3974.101.a37.
[2] Brian Alspach and Chris Godsil, editors. Cycles in Graphs. North-Holland Publishing Co., Amsterdam, 1985. https://www.elsevier.com/books/cycles-in-graphs/alspach/978-0-444-87803-8.
[3] Oleg Bogopolski. Introduction to group theory. EMS Textbooks in Mathematics. European Mathematical Society (EMS), Zürich, 2008. https://doi.org/10.4171/041.
[4] Chuan Chong Chen and Norman F. Quimpo. On strongly Hamiltonian abelian group graphs. 884:23–34, 1981. https://doi.org/10.1007/bfb0091805.
[5] Iren Darijani, Babak Miraftab, and Dave Morris. Arc-disjoint hamiltonian paths in Cartesian products of directed cycles, 2022. https://arxiv.org/pdf/2203.11017 (preprint).
[6] Reinhard Diestel. Locally finite graphs with ends: a topological approach, II. Applications. Discrete Math., 310(20):2750–2765, 2010. https://doi.org/10.1016/j.disc.2010.05.027.
[7] Reinhard Diestel. Locally finite graphs with ends: a topological approach, I. Basic theory. Discrete Math., 311(15):1423–1447, 2011. https://doi.org/10.1016/j.disc.2010.05.023.
[8] Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, fifth edition, 2018.
[9] Joshua Erde and Florian Lehner. Hamiltonian decompositions of 4-regular Cayley graphs of infinite abelian groups, 2020. https://arxiv.org/abs/2006.09759 (preprint).
[10] Agelos Georgakopoulos. Infinite Hamilton cycles in squares of locally finite graphs. Adv. Math., 220(3):670–705, 2009. https://doi.org/10.1016/j.aim.2008.09.014.
[11] Ganhewalage Jayantha Lanel et al. A survey on hamiltonicity in Cayley graphs and digraphs on different groups. Discrete Math. Algorithms Appl., 11(5):Article ID 1930002, 2019. https://doi.org/10.1142/s1793830919300029.
[12] B. Miraftab and T. Rühmann. From cycles to circles in Cayley graphs. arXiv preprint arXiv:1708.03476, 2017.
[13] Babak Miraftab and Tim Rühmann. Hamilton circles in Cayley graphs. Electron. J. Combin., 25(2):Paper No. 2.5, 17, 2018. https://doi.org/10.37236/7009.
[14] Babak Miraftab and Tim Rühmann. Two-ended quasi-transitive graphs. Discrete Mathematics, Algorithms and Applications, 2021, in press. https://doi.org/10.1142/S1793830922500239.
[15] Babak Miraftab and Konstantinos Stavropoulos. Splitting groups with cubic Cayley graphs of connectivity two. Algebr. Comb., 4(6):971–987, 2021. https://doi.org/10.5802/alco.
[16] C. St. J. A. Nash-Williams. Abelian groups, graphs and generalized knights. Proc. Cambridge Philos. Soc., 55:232–238, 1959. https://doi.org/10.1017/s0305004100033946.
[17] Peter Scott and Terry Wall. Topological methods in group theory. In Homological group theory (Proc. Sympos., Durham, 1977), volume 36 of London Math. Soc. Lecture Note Ser., pages 137–203. Cambridge Univ. Press, Cambridge-New York, 1979. https://doi.org/10.1017/cbo9781107325449.007.
[18] William R Scott. Group Theory. Prentice-Hall, Englewood Cliffs, NJ, 1964.
[19] Michio Suzuki. Group Theory, volume 247. Springer-Verlag, 1982. https://doi.org/10.1007/978-3-642-61804-8.
[20] David Witte and Joseph A. Gallian. A survey: Hamiltonian cycles in Cayley graphs. Discrete Math., 51(3):293–304, 1984. https://doi.org/10.1016/0012-365X(84)90010-4.
[21] David S. Witte. On Hamiltonian circuits in Cayley diagrams. Discrete Math., 38(1):99–108, 1982. https://doi.org/10.1016/0012-365X(82)90174-1.

Hamiltonicity in generalized quasi-dihedral groups ††thanks: Key Words: Cayley graphs, Hamiltonian double rays, Infinite graph, Infinite groups ††thanks: Mathematics Subject Classification 2010: 05C25, 05C45, 05C63, 20E06, 20F05.

Abstract

1 Introduction

Conjecture 1 ([12]).

Theorem 1.1.

Corollary 1.2.

2 Preliminaries

Definition 1.

Lemma 2.1.

Theorem 2.2.

3 The structure of GQD groups

Lemma 3.1.

Proof.

Lemma 3.2.

Corollary 3.3.

Lemma 3.4.

Proof.

Lemma 3.5.

Proof.

Lemma 3.6.

Corollary 3.7.

Lemma 3.8.

Theorem 3.9.

Proof.

Lemma 3.10.

Proof.

Theorem 3.11.

Proof.

3.1 Short cycles in Cayley graphs of two-ended generalized quasi-dihedral groups

Theorem 3.12.

Proof.

Theorem 3.13.

Proof.

4 Grids, Walls and Cylinders

Lemma 4.1.

Lemma 4.2.

Proof.

Lemma 4.3.

Proof.

Lemma 4.4.

Proof.

5 Proof of the main Theorem

Lemma 5.1.

Lemma 5.2.

Proof.

Proof of Theorem 1.1.

6 Final Remarks

6.1 Hamiltonian circles

Lemma 6.1.

Corollary 6.2.

Conjecture 2.

6.2 Hamilton-connectivity

Problem 1.

6.3 Decomposition and Uniqueness

Problem 2.

Problem 3.

References

Hamiltonicity in generalized quasi-dihedral groups ^†^†thanks: Key Words: Cayley graphs, Hamiltonian double rays, Infinite graph, Infinite groups ^†^†thanks: Mathematics Subject Classification 2010: 05C25, 05C45, 05C63, 20E06, 20F05.