A family of tetravalent half-arc-transitive graphs

Abstract

Alspach et al. (J. Austral. Math. Soc. 56(3) (1994) 391–402) constructed an infinite family of tetravalent graphs M(a; m, n) and proved that if $n\ge 9$ be odd and $a^3\equiv 1 (\mathrm{mod}~n)$, then M(a; 3, n) is half-arc-transitive. In this paper, we show that if $a^3\equiv 1 (\mathrm{mod}~n)$ , then M(a; 3, n) is an infinite family of tetravalent half-arc-transitive Cayley graphs for all integers n except 7 and 14.

1 Introduction

A graph $G=(V,E)$ is said to be vertex-transitive, edge-transitive and arc-transitive if the automorphism group of G, $\mathsf {Aut}(G)$, acts transitively on the vertices, on the edges and on the arcs of G respectively. It is known that an arc-transitive graph is both vertex-transitive and edge-transitive. However, a graph which is both vertex-transitive and edge-transitive may not be arc-transitive, the smallest example being the Holt graph [10] on 27 vertices. Such graphs are called half-arc-transitive graphs. For other definitions related to algebraic graph theory, one is referred to [9].

The study of half-arc-transitive graphs was initiated by Tutte [13], who proved that any half-arc-transitive graph is of even degree. Since any connected 2-regular is a cycle and a cycle is arc-transitive, the first possibility of finding a half-arc-transitive graph is a 4-regular or tetravalent graph. The first examples of tetravalent half-arc-transitive graphs were given by Bouwer [3] and the smallest example was given by Holt [10]. Though numerous papers have been published in the last 50 years, the classification of tetravalent half-arc-transitive graphs is not yet complete. In the absence of a complete classification, two major approaches have been fruitful so far: the first is to characterize half-arc-transitive graphs of some particular orders like $p^3,p^4,p^5,pq,2pq$, etc. [5,6,7,8], and the second is to come up with infinite families of half-arc-transitive graphs [4, 14].

In [1], Alspach et al. constructed an infinite family of tetravalent graphs M(a; m, n) and proved as follows.

Theorem 1.1

[1, Theorem 3.3]. Let $n\ge 9$ be odd and $a^3\equiv 1 (\mathrm{mod}~n)$. Then M(a; 3, n) is half-arc-transitive.

In this paper, we prove that M(a; 3, n) is half-arc-transitive for all integers n except 7 and 14. For this, we redefine M(a; 3, n) (as $\Gamma (n,a)$ in Definition 1.1) in a different way which helps us to prove the half-arc-transitivity of the entire family (not only when n is odd). It turns out that $\Gamma (n,a)$ is a family of Cayley graphs of order 3n and for $(n,a)=(9,4)$, we get the Holt graph. In fact, our definition (Definition 1.1) is a generalization of an alternative construction of the Holt graph (see the last paragraph of [10]).

DEFINITION 1.1

 Let n be a positive integer such that $3\mid \varphi (n)$, where $\varphi$ denotes the Euler totient function. Then ${\mathbb {Z}}^*_n$, the group of units of ${\mathbb {Z}}_n$, is a group of order a multiple of 3. Let a be an element of order 3 in ${\mathbb {Z}}^*_n$ and $b\equiv a^2(\mathrm{mod} ~n)$. Define $\Gamma (n,a)$ to be the graph with vertex-set ${\mathbb {Z}}_n\times {\mathbb {Z}}_3$ and the edge-set composed of edges of the form $(i,j)\sim (ai\pm 1,j-1)$ and $(i,j)\sim (bi\pm b,j+1)$, where the operations in the first and second coordinates are done modulo n and modulo 3, respectively.

It is obvious that $\Gamma (n,a)$ is tetravalent. One can check that $\Gamma (n,a)$ is a suitable redefinition of M(a; 3, n) and $\Gamma (9,4)$ is the Holt graph. It is also to be noted that for a particular n, we can have two graphs, $\Gamma (n,a)$ and $\Gamma (n,b)$. However, these two graphs are isomorphic via the automorphism $\tau : \Gamma (n,a)\rightarrow \Gamma (n,a^2)$ defined by $\tau (i,j)=(ai,-j)$. So, without loss of generality, we assume that $a<b$, where $a,b \in \{2,\ldots ,n-2\}$.

On the other hand, let n be a positive integer such that $a_1,b_1,a_2,b_2$ are four elements of order 3 in ${\mathbb {Z}}^*_n$ with $a_1b_1\equiv 1(\mathrm{mod}~n)$ and $a_2b_2\equiv 1(\mathrm{mod}~n)$. Then, by the above argument, $\Gamma (n,a_1)\cong \Gamma (n,b_1)$ and $\Gamma (n,a_2)\cong \Gamma (n,b_2)$. However, $\Gamma (n,a_1)$ may not be isomorphic to $\Gamma (n,a_2)$. For example, if $n=63$, we have $4\cdot 16\equiv 1(\mathrm{mod} ~63)$ and $22\cdot 43\equiv 1(\mathrm{mod} ~63)$, but $\Gamma (63,4)$ is not isomorphic to $\Gamma (63,22)$, as the odd girth of $\Gamma (63,4)$ is 9, whereas that of $\Gamma (63,22)$ is 21.

The definition of $\Gamma (n,a)$ requires that $3|\varphi (n)$. We discuss the form of n for which this holds. Let $n={p_1}^{\alpha _1}{p_2}^{\alpha _2}\cdots {p_k}^{\alpha _k}$, where the $p_i$ are primes. Then $\varphi (n)={p_1}^{\alpha _1-1}{p_2}^{\alpha _2-1}$ $\cdots {p_k}^{\alpha _k-1}$ $(p_1-1)(p_2-1)\cdots (p_k-1)$. As $3|\varphi (n)$, either $3|{p_i}^{\alpha _i-1}$ or $3|(p_i-1)$ for some i, i.e., 9|n or $p_i\equiv 1(\mathrm{mod}~3)$ for some i. Thus n is either of the form 9t or pt, where p is a prime of the form $1(\mathrm{mod}~3)$ and t is a positive integer.

At this junction, it is important to note the difference between our proof and the proof of [1].

• (1) First, the proof techniques are entirely different: While their proof is built on semiregular automorphisms and blocks, ours is based on 6-cycles present in the graph.

• (2) Second and most importantly, we prove that $\Gamma (n,a)$ is half-arc-transitive for all n except 7 and 14, i.e., n is not necessarily odd, so that we prove the result for a larger family of graphs.

In the next section, we prove the main results related to the automorphism group and half-arc-transitivity of $\Gamma (n,a)$. In the Appendix, we provide the SageMath [12] code for computing the automorphism group of $\Gamma (n,a)$.

2 Automorphisms of $\Gamma (n,a)$

Let $G=\mathsf {Aut}(\Gamma (n,a))$. We start by noting the following automorphisms of $\Gamma (n,a)$:

$$\begin{aligned} \begin{array}{lll} \alpha : (i,j) \mapsto (i+a^{-j},j);&~~\beta : (i,j)\mapsto (i,j+1);&~~\gamma : (i,j) \mapsto (-i,j). \end{array} \end{aligned}$$

It can be shown that $\alpha ,\beta ,\gamma \in G$ and $\circ (\alpha )=n,\circ (\beta )=3$ and $\circ (\gamma )=2$. Moreover, we have the following relations: $\alpha \beta =\beta \alpha ^{a^2},$ $\alpha \gamma =\gamma \alpha ^{-1}$ and $\beta \gamma =\gamma \beta$.

Theorem 2.1

$\Gamma (n,a)$ is a Cayley graph.

Proof

Let $H=\langle \alpha , \beta \rangle$. Clearly it forms a subgroup of G. Also, as $\circ (\alpha )=n,\circ (\beta )=3$ and $\alpha \beta =\beta \alpha ^{a^2}$, we have

$$\begin{aligned} H=\{\alpha ^i\beta ^j:0\le i \le n-1,0\le j \le 2\} \quad \text{ and } \quad |H|=3n=|\Gamma (n,a)|. \end{aligned}$$

We will show that H acts regularly on $\Gamma (n,a)$. As $|H|=|\Gamma (n,a)|$, it is enough to show that H acts transitively on $\Gamma (n,a)$. As $i\mapsto i+a^{-j}$ is a permutation of ${\mathbb {Z}}_n$ order n and $j\mapsto j+1$ is a permutation of ${\mathbb {Z}}_3$ order 3, the action of H on $\Gamma (n,a)$ is transitive. $\square$

Note that H is a semidirect product of $\langle \alpha \rangle$ and $\langle \beta \rangle$, as $\beta ^{-1}\alpha \beta =\alpha ^{a^2}$ and $a^2$ and n are coprime, and $\Gamma (n,a)=\mathrm{Cay}(H,S)$, where $S=\{\beta ^2\alpha ,\beta ^2\alpha ^{-1},\beta \alpha ^b,\beta \alpha ^{-b} \}$. We now recall a result on Hamiltonicity of Cayley graphs.

Theorem 2.2

[11, Theorem 3.3]. Every connected Cayley graph of a semidirect product of a cyclic group of prime order by an abelain group of odd order is Hamiltonian. $\square$

COROLLARY 2.1

If n is odd$\mathrm{,}$ then $\Gamma (n,a)$ is Hamiltonian .

Proof

By Theorem 2.1, we have $\Gamma (n,a)$ is a Cayley graph on H and H is a semidirect product of a cyclic group of order 3, namely $\langle \beta \rangle$, and another cyclic group of odd order n, namely $\langle \alpha \rangle$. Thus, by Theorem 2.2, $\Gamma (n,a)$ is Hamiltonian. $\square$

Theorem 2.3

$\Gamma (n,a)$ is edge-transitive.

Proof

As $\Gamma (n,a)$ is Cayley, it is vertex-transitive. Hence, it is enough to show that any two edges incident with (0, 0) can be permuted by an automorphism. As $\Gamma (n,a)$ is tetravalent, the four vertices adjacent to (0, 0) are namely: $(1,2),(-1,2),(b,1)$ and $(-b,1)$. Let us name the following edges as

$$\begin{aligned} \begin{array}{rlcrl} e_1: &{} (0,0)\sim (1,2)&{} ~~ &{}e_2: &{} (0,0)\sim (-1,2)\\ e_3: &{} (0,0)\sim (b,1)&{} ~~ &{}e_4: &{} (0,0)\sim (-b,1). \end{array} \end{aligned}$$

It is to be noted that $\gamma (e_1)=e_2$, $\alpha \beta \gamma (e_1)=~{\mathop {e_3}\limits ^{\leftarrow }}$ and $\gamma \alpha \beta \gamma (e_1)=~{\mathop {e_4}\limits ^{\leftarrow }}$. The reverse arrow on top denotes that the orientation of the edge is changed. Hence, the theorem follows. $\square$

For $n=7,14$, SageMath [12] computation shows that $\Gamma (n,a)$ is arc-transitive. Next, we prove that $\Gamma (n,a)$ is not arc-transitive if $n\ne 7,14$. For that, we show that there does not exist any graph automorphism $\varphi$ which maps the arc $e_3$ to $e_1$, i.e., $\varphi ((0,0))=(0,0)$ and $\varphi ((b,1))=(1,2)$.

The next theorem shows that there can not be an automorphism $\varphi$ for which $\varphi ((0,0))=(0,0)$ and $\varphi ((b,1))=(1,2)$ because $\varphi ((1,2))$ should be one of $\lbrace (b,1)$, $(-b,1)$, $(-1,2) \rbrace$.

Theorem 2.4

If $\varphi$ is an automorphism of $\Gamma (n,a)$ such that $n\ne 7,14$ and $\varphi ((0,0)=(0,0)$ and $\varphi ((b,1))=(1,2)$, then $\varphi ((1,2)) \notin \{(b,1),(-b,1),(-1,2)\}$. $\square$

Thus, from Theorems 2.1, 2.3 and 2.4, we obtain the following result.

Theorem 2.5

$\Gamma (n,a)$ is half-arc-transitive if $n\ne 7,14$. $\square$

3 Proof of Theorem 2.4

To prove Theorem 2.4, we prove a lemma and three theorems. Throughout this section, $\varphi$ denotes an automorphism of $\Gamma (n,a)$ and G denotes the full automorphsim group of $\Gamma (n,a)$.

Lemma 3.1

The following relations can not hold : 

• (1) $2a-4b=0$,

• (2) $2a+4b=0$ except for $n=9$,

• (3) $4a-2b=0$ except for $n=7,14$,

• (4) $4a+2b=0$ except for $n=18$,

• (5) $2a-2b=0$,

• (6) $2a+2b=0$,

• (7) $4a+4=0$,

• (8) $2a+6=0$,

• (9) $2(a+b-1)=0$,

• (10) $2(b-a+1)=0$,

• (11) $2(a-b+1)=0$,

• (12) $2(a+b+2)=0$,

• (13) $2(a-b-2)=0$.

Proof

• (1) $2a-4b=0$, i.e., $8=64$, i.e., $56=0$, i.e., $n \mid 56$ and hence $n \in \lbrace 7, 14, 28, 56 \rbrace$ and the possible values of b are 4, 11, 25, 25, respectively. In all these cases $2b \ne 4$, which is a contradiction.

• (2) $2a+4b=0$, i.e., $8=-64$, i.e., $72=0$, i.e., $n \mid 72$ and hence $n \in \lbrace 9, 18, 36, 72 \rbrace$ and the possible values of b are 7, 13, 25, 49. But the relation holds only if $n=9$ and $b=7$.

• (3) $4a-2b=0$, $8=64$, i.e., $56=0$, i.e., $n \mid 56$ and hence $n \in \lbrace 7, 14, 28, 56 \rbrace$ and the possible values of (a, b) are (2, 4), (9, 11), (9, 25), (9, 25), respectively. But the relation holds only if $n \in \lbrace 7,14\rbrace$.

• (4) $4a+2b=0$, i.e., $64=-8$, i.e., $72=0$, i.e., $n \mid 72$ and hence $n\in \lbrace 9, 18, 36, 72 \rbrace$ and the possible values of (a, b) are (4, 7), (7, 13), (13, 25), (25, 49), respectively. But the relation holds only if $n=18$.

• (5) $2a-2b=0$, i.e., $2a\equiv 2(\mathrm{mod}~n)$. If n being odd, then $a=1$, which is impossible. Let n be even and $n=2m$. Then we have $m \mid a-1$, i.e., $a=mt+1$, for some $t \in \mathbb Z$. As $a \ne 1$, so $a=m+1$, i.e., $a^3-1= m(m^2+3m+3)$. Note that irrespective of m is odd or even, $(m^2+3m+3)$ is odd, say $(2s+1)$, for some $s \in \mathbb Z$. So we have $a^3-1=m(2s+1)$, i.e., $a^3-1 \equiv m (\mathrm{mod}~n)$, which is a contradiction.

• (6) The proof is the same as (5)

• (7) $4a+4=0$, i.e., $4a\equiv -4(\mathrm{mod}~n)$. If n is odd, then $a=-1$, which is impossible. If n is even and $n=2m$, then we have $m \mid 2(a+1)$, i.e., $2a=mt-2$, for some $t \in \mathbb Z$. As $2a \ne -2$, so $2a=m-2$, i.e., $8(a^3-1)=m(m^2-6m+12)-16$. If m is even, then $(m^2-6m+12)$ is even, say 2u, for some $u \in \mathbb Z$. So we have $8(a^3-1)=2mu-16$, i.e., $8(a^3-1) \equiv -16(\mathrm{mod}~n)$, which is a contradiction. If m is odd, then $(m^2-6m+12)$ is odd, say $2v+1$, for some $v \in \mathbb Z$. So we have $8(a^3-1)=m(2v+1)-16$, i.e., $8(a^3-1) \equiv m-16(\mathrm{mod}~n)$, which is a contradiction as $m \ne 16$.

• (8) $2a+6=0$, i.e., $8=-216$, i.e., $224=0$, i.e., $n \mid 224$, i.e., $n \in \lbrace 7, 14, 28, 56, 112, 224 \rbrace$. However, in all these cases, the possible values of a does not allow $2a+6=0$.

• (9) $2(a+b-1)=0$, i.e., $2(1+a-b)=0$, i.e., $4a=0$, contradicting that a is a unit.

• (10) The proof is the same as (9).

• (11) $2(a-b+1)=0$, i.e., $2(1-a+b)=0$, i.e., $2(a-b+1)+2(1-a+b)=0$, i.e., $4=0$, which is a contradiction.

• (12) $2(a+b+2)=0$, i.e., $2(1+a+2b)=0$, i.e., $4(a+b+2)-2(1+a+2b)=0$, i.e., $2(a+3)=0$, i.e., $8=-216$, i.e., $224=0$, i.e., $n \mid 224$, i.e., $n \in \lbrace 7, 14, 28, 56, 112, 224 \rbrace$. In all these cases, $2a+6 \ne 0$, which is a contradiction.

• (13) $2(a-b-2)=0$, i.e., $2(1-a-2b)=0$, i.e., $2(a-b-2)+2(1-a-2b)=0$, i.e., $6b+2=0$, i.e., $2a+6=0$. The rest of the proof is the same as (8). $\square$

Theorem 3.1

If $\varphi \in G$ and $\varphi ((0,0))=(0,0),~ \varphi ((b,1))=(1,2)$, $\varphi ((1,2))=(-1,2)$ then $n=7$ or 14.

Proof

Consider the cycle $C: (0,0)\sim (b,1) \sim (a+b,2) \sim (1+a+b,0)\sim (a+1,1)\sim (1,2)\sim (0,0)$. Then $\varphi (C):(0,0)\sim (1,2) \sim \varphi ((a+b,2)) \sim \varphi ((1+a+b,0)) \sim \varphi ((a+1,1))\sim (-1,2)\sim (0,0)$. As $\varphi ((a+b,2)) \sim (1,2)$ and $\varphi ((0,0))=(0,0)$, so $\varphi ((a+b,2)) \in \lbrace (2b,0), (a \pm 1,1) \rbrace$. Again, $\varphi ((a+1,1)) \sim (-1,2)$ and $\varphi ((0,0))=(0,0)$ imply $\varphi ((a+1,1)) \in \lbrace (-2b,0), (-a \pm 1,1) \rbrace$. Also, $\varphi ((1+a+b,0)) \sim \varphi ((a+b,2))$ and $\varphi ((b,1))=(1,2)$ imply

$$\begin{aligned} \varphi ((1+a+b,0))\in & {} \lbrace (2a \pm b,1), (3,2), (1+ 2b,2), (b +a \pm 1, 0),\nonumber \\&(1-2b,2), (b-a \pm 1,0) \rbrace . \end{aligned}$$

(1)

If $\varphi ((a+1,1))=(-2b,0)$, then $\varphi ((1+a+b,0)) \sim \varphi ((a+1,1))$ and $\varphi ((1,2))=(-1,2))$ imply

$$\begin{aligned} \varphi ((1+a+b,0)) \in \lbrace (-3,2), (-2a \pm b,1) \rbrace . \end{aligned}$$

(2)

From Equations (1) and (2), we have

• either $-3=3$, i.e., $6=0$, i.e., $n=6$ which is impossible.

• or $-3=1+2b$, i.e., $2a+4b=0$, which is possible only when $n=9$ (by Lemma 3.1). However, direct SageMath computation for $n=9$ shows that such $\varphi$ does not exist.

• or $-3=1-2b$, i.e., $2a-4b=0$, which is impossible by Lemma 3.1.

• or $-2a \pm b=2a \pm b$, i.e., $4a=0$ or $4a-2b=0$ or $4a+2b=0$. Though the first one is impossible, the other two can hold only if $n \in \lbrace 7,14,18\rbrace$ (by Lemma 3.1). However, direct SageMath computation for $n=7,14$ and 18 shows that such a $\varphi$ does not exist.

Hence $\varphi ((a+1,1)) \ne (-2b,0)$.

If $\varphi ((a+1,1))=(-a+1,1)$, then $\varphi ((1+a+b,0)) \sim \varphi ((a+1,1))$ and $\varphi ((1,2))=(-1,2)$ imply

$$\begin{aligned} \varphi ((1+a+b,0)) \in \lbrace (-1+2b,2), (-b+a \pm 1,0) \rbrace . \end{aligned}$$

(3)

From Equations (1) and (3), we have

• either $-b+a \pm 1= b-a \pm 1$, i.e., $2(a-b)=0$ or $2(b-a+1)=0$ or $2(b-a-1)=0$, all of which are impossible by Lemma 3.1.

• or $-b+a \pm 1=b+a \pm 1$, i.e., $2b=0$ or$2a-2b=0$ or $2a+2b=0$, all of which are impossible by Lemma 3.1.

• or $-1+2b=3$, i.e., $2a-4b=0$, which is impossible by Lemma 3.1.

• or $-1+2b=1+2b$, i.e., $2=0$, which is a contradiction.

• or $-1+2b=1-2b$, i.e., $4a-2b=0$ which can hold only if $n=7$ or 14. (by Lemma 3.1.) However, direct SageMath computation for $n=7,14$ shows that such $\varphi$ does not exist.

Hence $\varphi ((a+1,1)) \ne (-a+1,1)$.

If $\varphi ((a+1,1))=(-a-1,1)$, then $\varphi ((1+a+b,0)) \sim \varphi ((a+1,1))$ and $\varphi ((1,2))=(-1,2))$ imply

$$\begin{aligned} \varphi ((1+a+b,0)) \in \lbrace (-1-2b,2), (-b-a \pm 1,0) \rbrace \end{aligned}$$

(4)

From Equations (1) and (4), we have

• either $-1-2b=3$, i.e., $2a+4b=0$, which can hold only if $n=9$ (by Lemma 3.1). However, direct SageMath computation rules out this possibility.

• or $-1-2b=1+2b$, i.e., $4a+2b=0$, which can hold only if $n=18$. (by Lemma 3.1). However, direct SageMath computation rules out this possibility.

• or $-1-2b=1-2b$, i.e., $2=0$, which is a contradiction.

• or $-b-a \pm 1= b-a \pm 1$, i.e., $2b=0$, or $2a+2b=0$, or $2a-2b=0$ all of which are impossible by Lemma 3.1.

• or $-b-a \pm 1=b+a \pm 1$, i.e., $2(b+a-1)=0$ or $2(b+a)=0$ (which are impossible by Lemma 3.1), but $2(1+a+b)=0$ may hold.

Therefore we have $\varphi ((1+a+b,0))=(1+a+b,0)$, $\varphi ((a+1,1))=(-a-1,1)$, $\varphi ((a+b,2))=(a+1,1)$ with $2(a+b+1)=0$.

Consider the cycle $C': (1+a+b,0)\sim (a+1,1) \sim (1+2b,2) \sim (2a,0) \sim (b+2,1) \sim (a+b,2) \sim (1+a+b,0)$. Then $\varphi (C'): (1+a+b,0)\sim (-a-1,1) \sim \varphi ((1+2b,2)) \sim \varphi ((2a,0)) \sim \varphi ((b+2,1)) \sim (a+1,1) \sim (1+a+b,0)$. Now $\varphi ((b+2,1)) \sim (a+1,1)$, $\varphi ((1+a+b,0))=(1+a+b,0)$ and $\varphi ((b,1))=(1,2)$ imply $\varphi ((b+2,1)) \in \lbrace (1+2b,2), (b+a-1,0)\rbrace$. Again $\varphi ((1+2b,2)) \sim (-a-1,1)$, $\varphi ((a+b+1,0))=(a+b+1,0)=(-a-b-1,0)$ and $\varphi ((1,2))=(-1,2)$ imply $\varphi ((1+2b,2)) \in \lbrace (-1-2b,2), (-b-a+ 1,0) \rbrace$. Also $\varphi ((2a,0)) \sim \varphi ((b+2,1))$ and $\varphi ((a+b,2))=(a+1,1)$ imply

$$\begin{aligned} \varphi ((2a,0)) \in \lbrace (b+2a \pm b,0), (a+3,1), (a+1-2b,1), (1+b-a \pm 1,2) \rbrace .\nonumber \\ \end{aligned}$$

(5)

Let $\varphi ((1+2b,2))=(-1-2b,2)$. Then $\varphi ((2a,0))\sim \varphi ((1+2b,2))$ and $\varphi ((a+1,1))=(-a-1,1)$ imply

$$\begin{aligned} \varphi ((2a,0)) \in \lbrace (-b-2a \pm b,0), (-a-3,1) . \end{aligned}$$

(6)

From Equations (5) and (6), we have

• either $-b-2a \pm b=b+2a \pm b$, i.e., $4a+4=0$ or $4a=0$ (which are impossible by Lemma 3.1) or $4a+2b=0$, which can hold only if $n=18$. However, direct SageMath computation rules out this possibility.

• or $-a-3=a+3$, i.e., $2a+6=0$, which is impossible by Lemma 3.1.

• or $-a-3=a+1-2b$, i.e., $2(a-b+2)=0$. Also, we had $2(a+b+1)=0$ previously. This yields $2a=4$, i.e., $n=7$ or 14.

Hence $\varphi ((1+2b,2))=(-1-2b,2)$ is possible only if $n=7$ or 14. Moreover, direct SageMath computation for $n=7$ and 14 confirms the possibility.

Let $\varphi ((1+2b,2))=(-b-a+1,0)$. Then $\varphi ((2a,0))\sim \varphi ((1+2b,2))$ and $\varphi ((a+1,1))=(-a-1,1)$ imply

$$\begin{aligned} \varphi ((2a,0)) \in \lbrace (-a-1+2b,1), (-1-b+a \pm 1,2) . \end{aligned}$$

(7)

From Equations (5) and (7), we have

• either $-1-b+a \pm 1=1+b-a \pm 1$, i.e., $2(b-a+1)=0$ or $2(a-b)=0$ or $2(a-b-2)=0$, all of which are impossible by Lemma 3.1.

• or $-a-1+2b=a+1-2b$, i.e., $2(a+1-2b)=0$, i.e., $2(a+b-2)=0$. Hence combining $2(a+b+1)=0$ and $2(a+b-2)=0$, we have $6=0$, which is impossible.

• or $-a-1+2b=a+3$, i.e., $2(a-b+2)=0$. Therefore, from $2(a+b+1)=0$ and $2(a-b+2)=0$, we have $2a=4$, i.e., $n=7$ or 14.

Hence $\varphi ((1+2b,2))=(-b-a+1,0)$ may be possible if $n=7$ or 14. Moreover, direct SageMath computation for $n=7$ and 14 confirms the possibility.

Therefore, for $\varphi \in G$, we can have $\varphi ((0,0))=(0,0),~ \varphi ((b,1))=(1,2)$, $\varphi ((1,2))=(-1,2)$ only if $n=7$ or 14. $\square$

Theorem 3.2

If $\varphi \in G$ and $\varphi ((0,0))=(0,0),~ \varphi ((b,1))=(1,2)$, then $\varphi ((1,2))\ne (-b,1)$.

Proof

Suppose that $\varphi \in G$ and $\varphi ((0,0))=(0,0),~ \varphi ((b,1))=(1,2)$ and $\varphi ((1,2))= (-b,1)$. Consider the cycle $C: (0,0)\sim (b,1) \sim (a+b,2) \sim (1+a+b,0)\sim (a+1,1)\sim (1,2)\sim (0,0)$. Then $\varphi (C):(0,0)\sim (1,2) \sim \varphi ((a+b,2)) \sim \varphi ((1+a+b,0)) \sim \varphi ((a+1,1))\sim (-b,1)\sim (0,0).$ As $\varphi ((a+b,2)) \sim (1,2)$ and $\varphi ((0,0))=(0,0)$, then $\varphi ((a+b,2)) \in \lbrace (2b,0), (a \pm 1,1) \rbrace$. Again, $\varphi ((a+1,1)) \sim (-b,1)$ and $\varphi ((0,0))=(0,0)$ imply $\varphi ((a+1,1)) \in \lbrace (-2,0), (-a \pm b,2) \rbrace$. Now as $\varphi ((1+a+b,0)) \sim \varphi ((a+b,2))$ and $\varphi ((b,1))=(1,2)$, we have

$$\begin{aligned} \varphi ((1+a+b,0))\in & {} \lbrace (2a \pm b,1), (3,2), (1+ 2b,2), (b +a \pm 1, 0),\nonumber \\&(1-2b,2), (b-a \pm 1,0) \rbrace . \end{aligned}$$

(8)

Depending upon the value of $\varphi ((a+1,1))$, one of the following three cases must hold, namely:

Case A: $\varphi ((a+1,1))=(-2,0)$),

Case B: $\varphi ((a+1,1))=(-a-b,2)$) or

Case C: $\varphi ((a+1,1))=(-a+b,2)$).

However, before resolving these three cases, we prove a claim which will be crucial in the following proof.

Claim. $\varphi ((-1-a-b,0)) \in \lbrace (-2a \pm b,1), (-3,2), (-1+ 2b,2), (-b +a \pm 1, 0),$ $(-1-2b,2), (-b-a \pm 1,0),(2a \pm 1,2), (3b,1), (b+2,1)$, $(1+a \pm b, 0),(b-2,1), (1-a \pm b,0) \rbrace .$

Proof of Claim. As $(-b,1)\sim (0,0)$ and $(-1,2) \sim (0,0)$, we have $\varphi ((-b,1)), \varphi ((-1,2))$ $\in \lbrace (b,1), (-1,2) \rbrace$.

Case 1: Let $\varphi ((-b,1))=(-1,2)$ and $\varphi ((-1,2))=(b,1)$. Consider the cycle $C': (0,0)\sim (-b,1) \sim (-a-b,2) \sim (-1-a-b,0)\sim (-a-1,1)\sim (-1,2)\sim (0,0)$, then $\varphi (C'):(0,0)\sim (-1,2) \sim \varphi ((-a-b,2)) \sim \varphi ((-1-a-b,0)) \sim \varphi ((-a-1,1))\sim (b,1)\sim (0,0)$. As $\varphi ((-a-b,2)) \sim (-1,2)$ and $\varphi ((0,0))=(0,0)$ then $\varphi ((-a-b,2)) \in \lbrace (-2b,0), (-a \pm 1,1) \rbrace$. $\varphi ((-a-1,1)) \sim (b,1)$ and $\varphi ((0,0))=(0,0)$ imply $\varphi ((-a-1,1)) \in \lbrace (2,0), (a \pm b,2) \rbrace$. Now $\varphi ((-1-a-b,0)) \sim \varphi ((-a-b,2))$ and $\varphi ((-b,1))=(-1,2)$ imply

$$\begin{aligned} \varphi (({-}1{-}a{-}b,0))\in & {} \lbrace ({-}2a \pm b,1), ({-}3,2), ({-}1{+} 2b,2), (-b +a \pm 1, 0),\nonumber \\&(-1-2b,2), (-b-a \pm 1,0) \rbrace . \end{aligned}$$

(9)

Case 2: Let $\varphi ((-b,1))=(b,1)$ and $\varphi ((-1,2))=(-1,2)$. Consider the cycle $C': (0,0)\sim (-b,1) \sim (-a-b,2) \sim (-1-a-b,0)\sim (-a-1,1)\sim (-1,2)\sim (0,0)$. Then $\varphi (C'):(0,0)\sim (b,1) \sim \varphi ((-a-b,2)) \sim \varphi ((-1-a-b,0)) \sim \varphi ((-a-1,1))\sim (b,1)\sim (0,0)$. As $\varphi ((-a-b,2)) \sim (b,1)$ and $\varphi ((0,0))=(0,0)$, then $\varphi ((-a-b,2)) \in \lbrace (-2,0), (a \pm b,2) \rbrace$. $\varphi ((-a-1,1)) \sim (-1,2)$ and $\varphi ((0,0))=(0,0)$ imply $\varphi ((-a-1,1)) \in \lbrace (-2b,0), (-a \pm 1,1) \rbrace$. Now $\varphi ((-1-a-b,0)) \sim \varphi ((-a-b,2))$ and $\varphi ((-b,1))=(b,1)$ imply

$$\begin{aligned} \varphi ((-1-a-b,0))\in & {} \lbrace (2a \pm 1,2), (3b,1), (b+2,1), (1+a \pm b, 0),\nonumber \\&(b-2,1), (1-a \pm b,0) \rbrace . \end{aligned}$$

(10)

Combining Cases (1) and (2), the claim follows.

We now turn towards the three cases mentioned earlier.

Case A: If $\varphi ((a+1,1))=(-2,0)$, then $\varphi ((1+a+b,0)) \sim \varphi ((a+1,1))$ and $\varphi ((1,2))=(-b,1)$ imply

$$\begin{aligned} \varphi ((1+a+b,0)) \in \lbrace (-3b,1), (-2a \pm 1,2) \rbrace . \end{aligned}$$

(11)

From Equations (8) and (11), we have

• either $-3b=2a \pm b$, i.e., $-2b=2a$ or $2b=-4$. By Lemma 3.1, this can hold only if $n=9$. However, direct SageMath computation for $n=9$ shows that such a $\varphi$ does not exist.

• or $-2a \pm 1=3$, i.e., $-2a=4$ or $-2a=2$, i.e., $4a+2b=0$ or $2a+2b=0$. By Lemma 3.1, $2a+2b=0$ can not hold and $4a+2b=0$ can hold only if $n=18$. However, direct SageMath computation for $n=18$ shows that such a $\varphi$ does not exist.

• or $-2a \pm 1=1-2b$, i.e., $2a=2b$, $2(b-a-1)=0$, both of which are impossible by Lemma 3.1.

• or $-2a \pm 1 = 1 +2b$, i.e., $2a+2b=0$ (which is impossible by Lemma 3.1) but

  $$\begin{aligned} 2a+2b+2=0~\text{ may } \text{ hold. } \end{aligned}$$

  (12)

When $\varphi ((a+1,1))=(-2,0)$, $\varphi ((1+a+b,0))=(1+2b,2)$, $\varphi ((a+b,2))=(a+1,1)$, then we have Equation (12). As $2a+2b+2=0$, i.e., $a+b+1=-a-b-1$, then $\varphi ((-1-a-b,0)) = (1+2b,2)$. But from Equations (9) and (10), we have $\varphi ((-1-a-b,0)) \ne (1+2b,2)$, which is a contradiction. Hence $\varphi ((a+1,1)) \ne (-2,0)$ and Case A can not hold.

Case B: If $\varphi ((a+1,1))=(-a-b,2)$, then $\varphi ((1+a+b,0)) \sim \varphi ((a+1,1))$ and $\varphi ((1,2))=(-b,1))$ imply

$$\begin{aligned} \varphi ((1+a+b,0)) \in \lbrace (-b-2,1), (-1-a\pm b,0) \rbrace . \end{aligned}$$

(13)

From Equations (8) and (13), we have as follows:

Case B(1): $-b-2=2a \pm b$, i.e., $2a+2b=0$, which is impossible by the Lemma 3.1, or

$$\begin{aligned} 2a+2b+2=0~ \text{ may } \text{ hold. } \end{aligned}$$

(14)

Case B(2): $-1-a\pm b=b+a \pm 1$, i.e., $2a+2b=0$ or $2a=0$ (which are impossible by Lemma 3.1), but $-1-a-b=b+a+1$, i.e.,

$$\begin{aligned} 2a+2b+2=0~ \text{ may } \text{ hold. } \end{aligned}$$

(15)

Case B(3): $-1-a \pm b=b-a \pm 1$. This gives rise to four equations, out of which three are impossible by Lemma 3.1, namely $2=0,~2b=0$ and $2a+2b=0$. The only possibility which remains is $-1-a+b=b-a-1$ and it is an identity.

So assuming this identity, we have $\varphi ((a+1,1))=(-a-b,2)$, $\varphi ((a+b+1,0))=(b-a-1,0)$ and $\varphi ((a+b,2))=(a-1,1)$. Similarly, we can show that $\varphi ((a-1,1))=(-a+b,2)$, $\varphi ((b-a+1,0))=(b+a-1,0)$ and $\varphi ((a-b,2))=(a+1,1)$. Now $\varphi ((a+b,2))=(a-1,1)$, $\varphi (((a-b,2))=(a+1,1)$ and $\varphi ((2,0)) \sim \varphi ((b,1))=(1,2)$ imply $\varphi ((2,0))=(2b,0)$.

Now, consider the cycle $C_2: (a+b+1,0) \sim (a+1,1) \sim (1,2) \sim (2b,0) \sim (2a+b,1) \sim (a+b+2,2) \sim (a+b+1,0).$ So $\varphi (C_2): (b-a-1,0) \sim (-a-b,2) \sim (-b,1) \sim \varphi ((2b,0)) \sim \varphi ((2a+b,1)) \sim \varphi ((a+b+2,2)) \sim (b-a-1,0).$

Again $\varphi ((0,0))=(0,0)$, $\varphi ((a+1,1))=(-a-b,2)$ and $\varphi ((2b,0)) \sim (-b,1)$ imply $\varphi ((2b,0)) \in \lbrace (-a+b,2), (-2,0) \rbrace$ and $\varphi (((a+b,2))=(a-1,1)$, $\varphi ((a+1,1))=(-a-b,2)$ and $\varphi ((a+b+2,2)) \sim (b-a-1,0)$ imply $\varphi ((a+b+2,2)) \in \lbrace (-b-a+2,2) , (-1-2b+a,1) \rbrace$. $\varphi ((1,2))=(-b,1)$ and $\varphi ((2a+b,1)) \sim \varphi ((2b,0))$ imply

$$\begin{aligned} \varphi ((2a+b,1)) \!\in \! \lbrace (-1+a \pm b,0), (-b+2,1), (-3b,1), (-2a \pm 1,2).\qquad \end{aligned}$$

(16)

Case B(3)(a): If $\varphi ((a+b+2,2))=(-b-a+2,2)$, then $\varphi ((a+b+1,0))=(b-a-1,0)$ and $\varphi ((2a+b,1)) \sim \varphi ((a+b+2,2))$ imply

$$\begin{aligned} \varphi ((2a+b,1)) \in \lbrace (a-1+3b,0), (-1-b+2a \pm 1,1) \rbrace . \end{aligned}$$

(17)

From Equations (16) and (17), we have

• either $-1-b+2a \pm 1= -b+2$, which implies either $2a-2b=0$ which is impossible by Lemma 3.1 or $4a-2b=0$ which is possible only for $n=7$ or 14. However, direct SageMath computation for $n=7$ and 14 shows that such a $\varphi$ does not exist.

• or $a-1+3b=-1-a \pm b$, i.e., $2a+4b=0$ which is possible only for $n=9$ or $2a+2b=0$, which is impossible by Lemma 3.1. And finally direct SageMath computation for $n=9$ shows that such $\varphi$ does not exist.

• or $-1-b+2a \pm 1=-3b$, i.e., $2a+2b=0$ or $2a+2b-2=0$, both of which are impossible by Lemma 3.1.

Hence $\varphi ((a+b+2,2)) \ne (-b-a+2,2)$.

Case B(3)(b): If $\varphi ((a+b+2,2))=(a-1-2b,1)$, then $\varphi ((a+b+1,0)=(b-a-1,0)$ and $\varphi ((2a+b,1)) \sim \varphi ((a+b+2,2))$ imply

$$\begin{aligned} \varphi ((2a+b,1)) \in \lbrace (b-a-3,0), (1-b-2a \pm b,2) \rbrace . \end{aligned}$$

(18)

From Equations (16) and (18), we have

• either $b-a-3=-1+a \pm b$, i.e., $2a+2b=0$ or $2a-2b+2=0$, both of which are impossible by Lemma 3.1.

• or $1-b-2a\pm b=-2a \pm 1$. These give rise to four equations, out of which three are impossible, by Lemma 3.1, namely $2=0,~2b=0$ and $2a-2b=0$. The only possibility which remains is $1-b-2a+b=-2a+1$ and it is an identity.

So assuming this to be the case, we have $\varphi ((2b,0))=(-2,0)$, $\varphi ((a+b+2,2))=(a-1-2b,1)$ and $\varphi ((2a+b,1))=(-2a+1,2)$.

Now consider the cycle $C_3: (2b,0) \sim (2a+b,1) \sim (a+b+2,2) \sim (1+a+3b,0) \sim (3a+1,1) \sim (3,2) \sim (2b,0)$. So $\varphi (C_3): (-2,0) \sim (-2a+1,2) \sim (a-1-2b,1) \sim \varphi ((1+a+3b,0)) \sim \varphi ((3a+1,1)) \sim \varphi ((3,2)) \sim (-2,0)$. Then $\varphi ((2b,0))=(-2,0)$, $\varphi ((2a+b,1))=(-2a+1,2)$ and $\varphi ((3,2)) \sim (-2,0)$ imply $\varphi ((3,2)) \in \lbrace (-3b,1), (-2a-1,2) \rbrace$. Again $\varphi ((2a+b,1))=(-2a+1,2)$, $\varphi ((a+b+1,0))=(b-a-1,0)$ and $\varphi ((1+a+3b,0)) \sim (a-1-2b,1)$ imply $\varphi ((1+a+3b,0)) \in \lbrace (1-2a-2b,2), (b-a-3,0) \rbrace$. Finally $\varphi ((2b,0))=(-2,0)$ and $\varphi ((3a+1,1)) \sim \varphi ((3,2))$ imply

$$\begin{aligned} \varphi ((3a+1,1)) \in \lbrace (-4,0), (-3a \pm b,2), (-2-2b,0), (-2b-a \pm 1,1) \rbrace .\nonumber \\ \end{aligned}$$

(19)

Case B(3)(b)(1): If $\varphi ((1+a+3b,0))=(1-2a-2b,2)$, then $\varphi ((3a+1,1)) \sim \varphi ((1+a+3b,0))$ implies

$$\begin{aligned} \varphi ((3a+1,1)) \in \lbrace (b-2a-2 \pm b,0), (a-2-2b \pm 1,1) \rbrace . \end{aligned}$$

(20)

From Equations (19) and (20), we have

• either $b-2a-2 \pm b=-4$, i.e., $2a-2b=0$ or $2a-2b-2=0$, both of which are impossible by Lemma 3.1.

• or $b-2a-2 \pm b= -2-2b$, i.e., $2a-2b=0$ or $2a-4b=0$, both of which are impossible by Lemma 3.1.

• or $a-2-2b \pm 1=-2b-a \pm 1$, i.e. $2a-2b=0$ or $2a=0$ or $4a-2b=0$. By Lemma 3.1, the first two are impossible and the third one may hold only for $n=7$ or 14. However, direct SageMath computation for $n=7$ and 14 shows that such a $\varphi$ does not exist.

So we have $\varphi ((1+a+3b,0))\ne (1-2b-2a,2)$.

Case B(3)(b)(2): If $\varphi ((1+a+3b,0))=(b-a-3,0)$, then $\varphi ((3a+1,1)) \sim \varphi ((1+a+3b,0))$ implies

$$\begin{aligned} \varphi ((3a+1,1)) \in \lbrace (a-1-3b \pm b,1), (b-1-3a \pm 1,2) \rbrace . \end{aligned}$$

(21)

From Equations (19) and (21), we have

• either $a-1-3b \pm b= -2b -a \pm 1$, i.e., $2a=0$ or $2a-2b=0$ or $2a-2b-2=0$, all of which are impossible by Lemma 3.1.

• or $1-b-3a \pm 1=-3a \pm b$. Out of the four relations that we get, three of them (namely, $2=0$, $2a-2b=0$ and $2b=0$) are invalid, by Lemma 3.1 and the fourth is an identity, i.e., $1-b-3a - 1=-3a - b$.

So we have $\varphi ((3a+1,1))=(-3a-b,2)$, $\varphi ((3,2))=(-3b,1)$, $\varphi ((a+1+3b,0))=(b-a-3,0)$. Similarly we can show that $\varphi ((3a-1,1))=(-3a+b,2)$ and $\varphi ((-a+1+3b,0))=(a+b-3,0)$.

Now $\varphi ((2b,0))=(-2,0)$, $\varphi ((3a+1,1))=(-3a-b,2)$, $\varphi ((3a-1,1))=(-3a+b,2)$ and $\varphi ((4b,0)) \sim \varphi ((3,2))=(-3b,1)$ imply $\varphi ((4b,0))=(-4,0)$.

Proceeding in this way, we can show that $\varphi ((2kb,0))=(-2k,0)$ for all $k \in \mathbb Z$. So we have $\varphi ((2,0))=(-2a,0)$, where $k=a$, which is a contradiction as we have shown earlier that $\varphi ((2,0))=(2b,0)$ and $2b \ne -2a$. Therefore, $\varphi ((a+b+1,0)) \ne (b-a-1,0)$.

Case B(1): When $\varphi ((a+1,1))=(-a-b,2)$, $\varphi ((1+a+b,0))=(2a+b,1)$, $\varphi ((a+b,2))=(2b,0)$, we have Equation (14). As $2a+2b+2=0$, i.e., $a+b+1=-a-b-1$, then $\varphi ((-1-a-b,0)) = (2a+b,1)$. But from Equations (9) and (10), we have $\varphi ((-1-a-b,0)) \ne (2a+b,1)$, which is a contradiction. Hence $\varphi ((1+a+b,0)) \ne (2a+b,1)$.

Case B(2): Now when $\varphi ((a+1,1))=(-a-b,2)$, $\varphi ((a+b+1,0))=(a+b+1,0)$, $\varphi ((a+b,2))=(a+1,1)$, then we have Equation (15). Consider the cycle $C_1: (a+b+1,0) \sim (a+1,1) \sim (1+2b,2) \sim (2a,0) \sim (b+2,1) \sim (a+b,2) \sim (a+b+1,0)$. Then $\varphi (C_1): (a+b+1,0) \sim (-a-b,2) \sim \varphi ((1+2b,2)) \sim \varphi ((2a,0)) \sim \varphi ((b+2,1)) \sim (a+1,1) \sim (a+b+1,0)$. Now $\varphi ((a+b+1,0))=(a+b+1,0)=(-a-b-1,0)$, $\varphi ((1,2))=(-b,1)$ and $\varphi ((1+2b,2)) \sim (-a-b,2)$ imply $\varphi ((1+2b,2)) \in \lbrace (-1-a+b,0), (-b-2,1) \rbrace$. Again, $\varphi ((b,1))=(1,2)$, $\varphi ((a+b+1,0))=(a+b+1,0)$ and $\varphi ((b+2,1)) \sim \varphi ((a+1,1))$ imply $\varphi ((b+2,1)) \in \lbrace (b+a-1,0), (1+2b,2) \rbrace$. Also, $\varphi ((a+1,1))=(-a-b,2)$ and $\varphi ((2a,0)) \sim \varphi ((1+2b,2))$ imply

$$\begin{aligned} \varphi ((2a,0))\in & {} \lbrace (-b-1+a \pm b,1), (-a-b+2,2), (-1-2a \pm 1,0),\nonumber \\&(-a-3b,2) \rbrace . \end{aligned}$$

(22)

Case B(2)(a): Now if $\varphi ((b+2,1))=(b+a-1,0)$, then $\varphi ((a+b,2))=(a+1,1)$ and $\varphi ((2a,0)) \sim \varphi ((b+2,1))$ imply

$$\begin{aligned} \varphi ((2a,0)) \in \lbrace (a+1-2b,1), (1+b-a \pm 1,2) \rbrace . \end{aligned}$$

(23)

From Equations (22) and (23), we have

• either $1+b-a \pm 1=-a-b+2$, i.e., $2b=0$ or $2a-2b=0$, both of which are impossible by Lemma 3.1.

• or $1+b-a \pm 1= -a-3b$, i.e., $4b=0$ which is impossible or $4a+2b=0$, which, by Lemma 3.1, holds only if $n=18$. However, direct SageMath computation for $n=18$ shows that such a $\varphi$ does not exist.

• or $a+1-2b= -b-1+a \pm b$, i.e., $2=0$ or $2a-2b=0$, both of which are impossible by Lemma 3.1.

Hence $\varphi ((b+2,1)) \ne (b+a-1,0)$.

Case B(2)(b): Now if $\varphi ((b+2,1))=(1+2b,2)$, then $\varphi ((a+b,2))=(a+1,1)$ and $\varphi ((2a,0)) \sim \varphi ((b+2,1))$ imply

$$\begin{aligned} \varphi ((2a,0)) \in \lbrace (a+3,1), (b+2a \pm b,0) \rbrace . \end{aligned}$$

(24)

From Equations (22) and (24), we have

• either $a+3=-b-1+a \pm b$, i.e., $4=0$ or $2a+4b=0$, which, by Lemma 3.1, can hold only if $n=9$. However, direct SageMath computation for $n=9$ shows that such a $\varphi$ does not exist.

• or $b+2a \pm b=-1-2a \pm 1$, i.e., $2(a+b+2)=0$ or $4a=0$ or $2a+4b=0$ or $4a+2b=0$. By Lemma 3.1, the first two are impossible and the next two can hold only if $n=9$ or 18. But those are also ruled out by SageMath computation.

Hence $\varphi ((b+2,1)) \ne (1+2b,2)$ and hence $\varphi ((a+1,1))\ne (-a-b,2)$, i.e., Case B can not hold.

Case C: If $\varphi ((a+1,1))=(-a+b,2)$, then $\varphi ((1,2))=(-b,1)$ and $\varphi ((a+b+1,0)) \sim \varphi ((a+1,1))$ imply

$$\begin{aligned} \varphi ((1+a+b,0)) \in \lbrace (-b+2,1), (-1+a\pm b,0) \rbrace . \end{aligned}$$

(25)

From Equations (8) and (25), we have

• either $-b+2=2a \pm b$, i.e., $2a-2b=0$ or $2(a+b-1)=0$, both of which are impossible by Lemma 3.1.

• or $-1+a\pm b=b-a\pm 1$, i.e., $2a=0$ or $2a-2b=0$ or $2(a-b-1)=0$ and all of them are ruled out by Lemma 3.1.

• or $-1+a \pm b = b+a \pm 1$. This gives rise two four conditions, out of which three (namely, $2=0$, $2a+2b=0$ and $2b=0$) are ruled out by Lemma 3.1 and the fourth one is the identity $-1+a+b=b+a-1$.

So we have $\varphi ((a+b+1,0))=(a-1+b,0)$, $\varphi (((a+b,2))=(a+1,1)$ and $\varphi ((a+1,1))=(-a+b,2)$.

Similarly we can show that $\varphi ((-a+b+1,0))=(-a-1+b,0)$, $\varphi (((a-b,2))=(a-1,1)$ and $\varphi ((a-1,1))=(-a-b,2)$.

Now $\varphi ((a+b,2))=(a+1,1)$, $\varphi (((a-b,2))=(a-1,1)$ and $\varphi ((2,0)) \sim \varphi ((b,1))=(1,2)$ imply $\varphi ((2,0))=(2b,0)$.

Consider the cycle $C_2: (a+b+1,0) \sim (a+1,1) \sim (1,2) \sim (2b,0) \sim (2a+b,1) \sim (a+b+2,2) \sim (a+b+1,0)$. So $\varphi (C_2): (a-1+b,0) \sim (-a+b,2) \sim (-b,1) \sim \varphi ((2b,0)) \sim \varphi ((2a+b,1)) \sim \varphi ((a+b+2,2)) \sim (a-1+b,0)$. Then $\varphi ((0,0))=(0,0)$, $\varphi ((a+1,0))=(-a+b,2)$ and $\varphi ((2b,0)) \sim (-b,1)$ imply $\varphi ((2b,0)) \in \lbrace (-a-b,2), (-2,0) \rbrace$. Again, $\varphi (((a+b,2))=(a+1,1)$, $\varphi ((a+1,1))=(-a+b,2)$ and $\varphi ((a+b+2,2)) \sim (a-1+b,0)$ imply $\varphi ((a+b+2,2)) \in \lbrace (b-a+2,2) , (1-2b+a,1) \rbrace$. Also, $\varphi ((1,2))=(-b,1)$ and $\varphi ((2a+b,1)) \sim \varphi ((2b,0))$ imply

$$\begin{aligned} \varphi ((2a+b,1)) \in \lbrace (-1-a \pm b,0), (-b-2,1), (-3b,1), (-2a \pm 1,2) \rbrace .\nonumber \\ \end{aligned}$$

(26)

Case C(1): If $\varphi ((a+b+2,2))=(b-a+2,2)$, then $\varphi ((a+b+1,0))=(a+b-1,0)$ and $\varphi ((2a+b,1)) \sim \varphi ((a+b+2,2))$ imply

$$\begin{aligned} \varphi ((2a+b,1)) \in \lbrace (a-1+3b,0), (1-b+2a \pm 1,1) \rbrace . \end{aligned}$$

(27)

From Equations (26) and (27), we have

• either $1-b+2a \pm 1= -b-2$, i.e., $2a+2b=0$ or $4a+2b=0$. By Lemma 3.1, the first is an impossibility and the second one can hold only if $n=18$. However, that is also ruled out by SageMath computation for $n=18$.

• or $a-1+3b=-1-a \pm b$, i.e., $2a+2b=0$ or $2a+4b=0$. By Lemma 3.1, the first is an impossibility and the second one can hold only if $n=9$. However, that is also ruled out by SageMath computation for $n=9$.

• or $1-b+2a \pm 1=-3b$, i.e., $2a+2b=0$, which is impossible by Lemma 3.1 but,

  $$\begin{aligned} 2a+2b+2=0~\text{ may } \text{ hold. } \end{aligned}$$

  (28)

When $\varphi ((a+b+1,0))=(a-1+b,0)$, $\varphi (((a+b,2))=(a+1,1)$ and $\varphi ((a+1,1))=(-a+b,2)$, then we have Equation (28). As $2a+2b+2=0$, i.e., $a+b+1=-a-b-1$, then $\varphi ((-1-a-b,0)) = (a-1+b,0)$. But from Equations (9) and (10), we have $\varphi ((-1-a-b,0)) \ne (a-1+b,0)$, which is a contradiction. Hence $\varphi ((a+b+2,2)) \ne (b-a+2,2)$.

Case C(2): If $\varphi ((a+b+2,2))=(a+1-2b,1)$, then $\varphi ((a+b+1,0)=(a-1+b,0)$ and $\varphi ((2a+b,1)) \sim \varphi ((a+b+2,2))$ imply

$$\begin{aligned} \varphi ((2a+b,1)) \in \lbrace (b+a-3,0), (1+b-2a \pm b,2) \rbrace . \end{aligned}$$

(29)

From Equations (26) and (29), we have

• either $b+a-3=-1-a \pm b$, i.e., $2a-2b=0$ or $2a+2b-2=0$, both of which are impossible by Lemma 3.1.

• or $1+b-2a\pm b=-2a \pm 1$. This gives rise to four conditions, out of which three, namely $2b=0$, $2-0$ and $2a+2b=0$, are ruled out, by Lemma 3.1 and the fourth one is the identity $1+b-2a-b=-2a+1$.

So we have $\varphi ((2a+b,1))=(-2a+1,2)$. Also previously, we had $\varphi ((2b,0))=(-2,0)$ and $\varphi ((a+b+2,2))=(1-2b+a,1)$.

Now consider the cycle $C_3: (2b,0) \sim (2a+b,1) \sim (a+b+2,2) \sim (1+a+3b,0) \sim (3a+1,1) \sim (3,2) \sim (2b,0)$. So $\varphi (C_3): (-2,0) \sim (-2a+1,2) \sim (1+a-2b,1) \sim \varphi ((1+a+3b,0)) \sim \varphi ((3a+1,1)) \sim \varphi ((3,2)) \sim (-2,0)$. Now, $\varphi ((2b,0))=(-2,0)$, $\varphi ((2a+b,1))=(-2a+1,2)$ and $\varphi ((3,2)) \sim (-2,0)$ imply $\varphi ((3,2)) \in \lbrace (-3b,1), (-2a-1,2) \rbrace$. Again $\varphi ((2a+b,1))=(-2a+1,2)$, $\varphi ((a+b+1,0))=(a+b-1,0)$ and $\varphi ((1+a+3b,0)) \sim (1+a-2b,1)$ imply $\varphi ((1+a+3b,0)) \in \lbrace (2b+1-2a,2), (a+b-3,0) \rbrace$. Also, $\varphi ((2b,0))=(-2,0)$ and $\varphi ((3a+1,1)) \sim \varphi ((3,2))$ imply

$$\begin{aligned} \varphi ((3a+1,1)) \in \lbrace (-4,0), (-3a \pm b,2), (-2-2b,0), (-2b-a \pm 1,1) \rbrace .\nonumber \\ \end{aligned}$$

(30)

Case C(2)(a): If $\varphi ((1+a+3b,0))=(2b+1-2a,2)$, then $\varphi ((3a+1,1)) \sim \varphi ((1+a+3b,0))$ implies

$$\begin{aligned} \varphi ((3a+1,1)) \in \lbrace (2a+b-2 \pm b,0), (2+a-2b \pm 1,1) \rbrace . \end{aligned}$$

(31)

From Equations (30) and (31), we have

• either $2+a-2b \pm 1=-2b-a \pm 1$, i.e. $2a+2b=0$ or $2a=0$ (which are impossible by Lemma 3.1) or $4a+2b=0$ which can hold only if $n=18$. But direct SageMath computation for $n=18$ ruled out this case.

• or $2a+b-2 \pm b= -2-2b$, i.e., $2a+2b=0$ (impossible by Lemma 3.1) or $2a+4b=0$, which can hold only if $n=9$. But direct SageMath computation ruled out this possibility.

• or $2a+b-2 \pm b=-4$, i.e., $2a+2b=0$, which is impossible by Lemma 3.1 but

  $$\begin{aligned} 2a+2b+2=0~\text{ may } \text{ hold. } \end{aligned}$$

  (32)

Thus, if $\varphi ((a+b+1,0))=(a-1+b,0)$, $\varphi (((a+b,2))=(a+1,1)$ and $\varphi ((a+1,1))=(-a+b,2)$ holds, then we have $2a+2b+2=0$. As $2a+2b+2=0$, i.e., $a+b+1=-a-b-1$, then $\varphi ((-1-a-b,0)) = (a-1+b,0)$. But from Equations (9) and (10), we have $\varphi ((-1-a-b,0)) \ne (a-1+b,0)$, which is a contradiction. Thus, Equation (32) does not hold.

So we have $\varphi ((1+a+3b,0))\ne (2b+1-2a,2)$.

Case C(2)(b): If $\varphi ((1+a+3b,0))=(a+b-3,0)$, then $\varphi ((3a+1,1)) \sim \varphi ((1+a+3b,0))$ implies

$$\begin{aligned} \varphi ((3a+1,1)) \in \lbrace (1+a-3b \pm b,1), (b+1-3a \pm 1,2) \rbrace . \end{aligned}$$

(33)

From Equations (30) and (33), we have

• either $1+a-3b \pm b= -2b -a \pm 1$, i.e., $2a=0$ or $2a+2b=0$ or $2a-2b=0$ or $2a-2b+2=0$, all of which are impossible by Lemma 3.1.

• or $b+1-3a \pm 1=-3a \pm b$. This gives rise to four conditions, out of which three, namely $2=0$, $2a+2b=0$ and $2b=0$, are ruled out, by Lemma 3.1 and fourth one is the identity $b+1-3a-1=-3a+b$.

So we have $\varphi ((3a+1,1))=(-3a+b,2)$, $\varphi ((3,2))=(-3b,1)$, $\varphi ((a+1+3b,0))=(a+b-3,0)$.

Similarly we can show that $\varphi ((3a-1,1))=(-3a-b,2)$ and $\varphi ((-a+1+3b,0))=(-a+b-3,0)$.

Now $\varphi ((2b,0))=(-2,0)$, $\varphi ((3a+1,1))=(-3a+b,2)$, $\varphi ((3a-1,1))=(-3a-b,2)$ and $\varphi ((4b,0)) \sim \varphi ((3,2))=(-3b,1)$ imply $\varphi ((4b,0))=(-4,0)$.

Proceeding this way, we can show that $\varphi ((2kb,0))=(-2k,0)$, for all $k \in \mathbb Z$. So we have $\varphi ((2,0))=(-2a,0)$, where $k=a$, which is a contradiction as we have shown that $\varphi ((2,0))=(2b,0)$ and $2b \ne -2a$. Therefore, we have $\varphi ((a+1,1))\ne (-a+b,2)$ and Case C can not hold.

As none of the cases A, B and C hold, the assumption that $\varphi ((1,2)) = (-b,1)$ is wrong. Hence the lemma follows. $\square$

Theorem 3.3

If $\varphi \in G$ and $\varphi ((0,0))=(0,0)$, $\varphi ((b,1))=(1,2)$, $\varphi ((1,2))=(b,1)$, then $n=7$ or 14.

Proof

The proof follows as in the proof of Theorem 3.1. For a detailed proof, one can see the proof of Theorem 4.3 [2]. $\square$

Now, the proof of Theorem 2.4 follows from Theorems 3.1, 3.2 and 3.3.

4 Open issues

In this paper, we proved the half-arc-transitivity of an infinite family of tetravalent Cayley graphs. However, a few issues are still pending and can be topics for further research.

• (1) Full Automorphism Group. It was shown that $\langle \alpha ,\beta ,\gamma \rangle$ is a subgroup of the full automorphism group. It remains to be shown (as observed in SageMath) that $G=\langle \alpha ,\beta ,\gamma \rangle$ for $n\ne 7,14$.

• (2) Structural Properties of $\Gamma (n,a)$. We have shown that $\Gamma (n,a)$ is Hamiltonian if n is odd. However, the Hamiltonicity for even values of n is still unresolved. Similarly, other structural properties like girth, diameter, domination number are few open issues.

Appendix

Appendix A: Sage Code for $\Gamma (n,a)$ for $n=7, a=2$: