Abstract

Relying on the Classification of Finite Simple Groups it was shown by Feng and Xu (Discrete Math., 2005) that every quartic Cayley graph of a regular $p$-group, $p\neq 2,5$, is normal. In this paper a CFSG-free proof of Feng-Xu theorem is given. Along the way it is also proved that for an arbitrary $p$-group $G$ with a minimum set $\{a,b\}$ of two generators, in the corresponding Cayley graph $\mathrm{Cay}(G,\{a,a^{-1},b,b^{-1}\})$ the induced action of vertex stabilizer on the neighbors’ set is contained in the dihedral group $D_{8}$.

Keywords: classification of finite simple groups, regular $p$-group, Cayley graph, normal graph, automorphism group.

1 Historic background

There are many important results in algebraic graph theory that depend heavily on the Classification of Finite Simple Groups (CFSG, hereafter). Still, we are of the opinion that one should, whenever possible, look for direct, more combinatorial proofs of these results, proofs that shed light on the intrinsic reasons as to why “particular combinatorial objects behave the way they do” (see [9, 10, 24]).

A fairly good example of what we have in mind is the extensive knowledge that has been aquired on cubic arc-transitive graphs without having to adhere to CFSG. It all started with the famous Tutte’s theorem which states, among other, that the order of vertex stabilizers of such graphs is bounded (see [28, 29]), following which a total of 17 different types of such graphs have been identified, depending on transitive action of the full automorphism group and their subgroups on arcs of different lengths (see [7, 8] for details).

The situation changes drastically when one moves to quartic arc-transitive graphs. One crucial distinction is that such graphs can have arbitrarily large vertex stabilizers, which makes their analysis quite a bit more demanding. There are several different reasons to study this class of graphs, supported also by an abundant research activity (see for example [11, 12, 14, 19, 20, 23, 25, 26, 30, 31, 32]).

One is that, having essentially answered most of relevant questions about cubic arc-transitive graphs, valency $4$ seems the natural next step. Also, in general, an arc-transitive graph containing a one-regular subgroup with a local cyclic action gives rise to a map on an appropriate orientable surface. (A one-regular subgroup of automorphisms acts regularly on the arc set of the graph.) Maps have received a lot of attention per se, but an even more intriguing facet of maps is their connection to certain open problems in graph theory, such as the long standing Lovász hamiltonicity problem for vertex-transitive graphs which asks whether every vertex-transitive graph has a Hamilton path (see [21]), with its variant for Cayley graphs asking for existence of a Hamilton cycle. (Given a group $G$ and an inverse closed subset $S$ of $G\setminus\{1\}$, the Cayley graph ${\rm Cay}(G,S)$ has vertex set $G$ and edges of the form $[g,gs]$, where $g\in G$ and $s\in S$. Unless specified otherwise, in this paper, Cayley graphs are assumed to be connected, that is $S$ generates $G$.) In [6, 18, 15, 16, 17, 18] cubic regular maps associated with cubic one-regular graphs have been used as a tool for constructing Hamilton cycles/paths for certain classes of cubic Cayley graphs. It is expected that quartic regular maps are likely to play a similar role in resolving the Lovász hamiltonicity problem for additional classes of cubic Cayley graphs.

Another one, and a focus of this paper, is an important result about normality of quartic Cayley graphs of regular $p$-groups, due to Feng and Xu [13]. Verbatim, their statement is as follows.

Theorem 1.1.

Let $p$ be a prime and $G$ a regular $p$-group with $p\neq 2,5$. Let $X={\rm Cay}(G,S)$ be a connected tetravalent Cayley graph on $G$. Then $\hbox{{\rm Aut}}({\rm Cay}(G,S))$ is the semidirect product of $R(G)$ with $\hbox{{\rm Aut}}(G,S)$.

Here $R(G)$ is the right regular representation of $G$. (As a word of attention, instead of the right regular representation we will be using the left regular representation of the group in question, and the symbol will be just $G$.) Next, $\hbox{{\rm Aut}}(G,S)$ is the subgroup of the automorphism group of $G$ fixing $S$ setwise, and of course “tetravalent” stands for “quartic” here. Also the condition that ${\rm Cay}(G,S)$ is the semidirect product of $R(G)$ with $\hbox{{\rm Aut}}(G,S)$ is precisely the definiton of the graph ${\rm Cay}(G,S)$ being normal, that is, the group $G$ being normal in $\hbox{{\rm Aut}}({\rm Cay}(G,S))$, the terminology used hereafter. Finally, recall that a $p$-group $G$ is regular if for any two $x,y\in G$ there exists $c\in G^{\prime}=[G,G]$ such that

$$(xy)^{p}=x^{p}y^{p}c^{p}.$$ (1)

(For example, note that any $p$-group that is either abelian, or of exponent $p$, or of nilpotency class less than $p$, is neceessarily regular.)

The original proof of Theorem 1.1 is CFSG-dependant. The authors first establish solvability of the full automorphism group of such a graph using CFSG, and then proceed to obtain normality with a combination of group-theoretic and combinatorial arguments.

Our aim is to give a CFSG-free proof of this result, a proof that is essentially combinatorial in nature, save for a couple of group-theoretic tools. We do this by first showing that in a quartic Cayley graph of an arbitrary $p$-group with a minimum generating set of two elements, the restriction of a vertex stabilizer of the full automorphism group to the neighbors’ set is contained in the dihedral group $D_{8}$ (see Theorem 3.2). This forces the full automorphism group to be a $\{2,p\}$-group and thus solvable, freeing ourselves from having to rely on CFSG in the proof of Theorem 1.1. Also, this means that the $2$-factors arising from the two generators are invariant under the action of the full automorphism group on the edge set. As observed in Proposition 4.1, normality of a Cayley graph of a $p$-group is equivalent to the set of oriented $2$-factors being invariant under the action of the full automorphism group. This is then used in the context of regular $p$-groups to obtain an alternative proof of Theorem 1.1.

2 Preliminaries

In this paper, all groups and graphs are assumed to be finite. By ${\hbox{\sf Z\kern-4.29993ptZ}}_{n}$, $n\geq 2$, we denote the cyclic group of order $n$, and by $C_{n}$, $n\geq 3$, the cycle (the connected graph of valency $2$) of length $n$. Given a graph $X$, we let $V(X)$, $E(X)$, $A(X)$ and $\hbox{{\rm Aut}}(X)$ denote, respectively, the vertex set, the edge set, the arc set and the automorphism group of $X$.

For a permutation group $G$ acting on a set $V$ (not necessarily transitive), and an element $g\in G$, a subset $B$ of $V$ is said to be invariant under the action of $g$ (in short, $g$-invariant) if $B\cap g(B)$ is either empty or coincides with $B$. Furthermore, the subset $B$ is $G$-invariant if it is $g$-invariant for all $g\in G$.

With regards to group-theoretic tools, two classical theorems – the Burnside Basis Theorem (sometimes also referred to as Frattini–Burnside Theorem) and the Burnside theorem on solvability of $\{p,q\}$-groups, $p,q$ primes – are used. Recall that the intersection of all maximal subgroups of $G$ is the Frattini subgroup $\Phi(G)$.

Theorem 2.1.

(Burnside Basis Theorem [5]) If $G$ is a finite $p$-group, then

$$\Phi(G)=G^{\prime}G^{p},$$

where $G^{\prime}=[G,G]$ is the commutator subgroup and $G^{p}=\{g^{p}|g\in G\}$. Moreover, $G/\Phi(G)$ is an elementary abelian $p$-group (and so a $\mathbb{F}_{p}$-vector space), and

$$d(G)=\dim_{\mathbb{F}_{p}}(G/\Phi(G)).$$

where $d(G)$ is the minimum number of generators of $G$.

Theorem 2.2.

(Burnside[3, 4]) Every finite group whose order is divisible by at most two distinct primes is solvable.

Hereafter, let $G=\langle a,b\rangle$ be a $p$-group, $p$ an odd prime, let

$$X=\rm{Cay}(G,S),\rm{where}\ S=\{a^{\pm 1},b^{\pm 1}\},$$ (2)

be the corresponding connected undirected quartic Cayley graph, let $A=\hbox{{\rm Aut}}(X)$, and let $A_{1}$ denote the stabilizer of the identity vertex $1\in G$.

We will think of the edges of $X$ as colored by the generators $a$ and $b$. More precisely, letting $s\in S$ and $g\in G$, we say that the arc $(g,gs)$ is an arc of oriented color $s$, or simply an $s$-arc. By extension, we say that the edge $[g,gs]=\{(g,gs),(gs,g)\}$ is an edge of color $s$, or simply an $s$-edge. (Here no distinction is made between oriented colors $s$ and $s^{-1}$.) Further, we let $\overrightarrow{E_{s}}$ denote the set of all $s$-arcs of $X$, and by $E_{s}$ the set of all $s$-edges of $X$. Clearly, the set $E_{s}$ induces a $2$-factor of $X$ consisting of cycles of color $s$ and length the order $|s|$ of $s$, so that ${\cal E}=\{E_{a},E_{b}\}$ is a decomposition of $E(X)$ into $2$-factors of colors $a$ and $b$. Similarly, $\overrightarrow{E_{s}}$ induces a union of color-oriented cycles of length $|s|$, referred to as $s$-cycles, so that ${\cal A}=\{\overrightarrow{E_{a}},\overrightarrow{E}_{a^{-1}},\overrightarrow{E_{b}},\overrightarrow{E}_{b^{-1}}\}$ is a decomposition of $A(X)$.of length

More generally, let $g\in G$, and let $(s_{0},s_{1},\dots,s_{k-1})$ be a sequence of generators $s_{i}\in S$, $i\in{\hbox{\sf Z\kern-4.29993ptZ}}_{k}$. A $k$-arc (of length $k$) of the form $(g,gs_{0},gs_{0}s_{1},\dots,gs_{0}s_{1}\dots s_{k-1})$ will be referred to as an $(s_{0},s_{1},\dots,s_{k-1})$-arc. Of course, when $s_{k-1}=s_{0}$ we have an oriented cycle of length $k$. As defined in the preceding paragraph, an $s$-cycle is just a simplified terminology for an $(s,s,\dots,s)$-cycle of corresponding length $k=|s|$.

Some additional terminology is needed for $2$-arcs and $3$-arcs. Let $r,s\in S$. For an $(r,s)$-arc we will use a shorthand notation $rs$-arc. Such a $2$-arc is called monochromatic if $r=s$, and is called diverse otherwise. The monochromatic $2$-arcs are precisely all $aa$-arcs and $bb$-arcs (and of course their counterparts $a^{-1}a^{-1}$-arcs and $b^{-1}b^{-1}$-arcs). Hence diverse $2$-arcs are $a^{\pm 1}b^{\pm 1}$-arcs and $b^{\pm 1}a^{\pm 1}$-arcs.

Similarly, given $r,s,t\in S$, we use a shorthand notation $rst$-arc for any $(r,s,t)$-arc. A special role is played by $3$-arcs with underlying edges of alternating colors, that is, $rsr^{\pm 1}$-arcs, $s\neq r,r^{-1}$. Such arcs are called alternating $3$-arcs, and are precisely: $a^{\pm 1}b^{\pm 1}a^{\pm 1}$-arcs and $b^{\pm 1}a^{\pm 1}b^{\pm 1}$-arcs.

3 Local rigidity in quartic Cayley graphs of $p$–groups

Let $\pi:G\to\overline{G}=G/G^{\prime}$ be the natural projection. For $g\in G$ we denote $\overline{g}=gG^{\prime}$. In particular, $\overline{S}=\{\overline{s}\ |\ s\in S\}$. We consider the action of the quotient group $\overline{G}$ on the quotient graph $\overline{X}=\mathrm{Cay}(\overline{G},\overline{S})$ of the graph $X$ given in (2). We start with a lemma, the proof of which is a straighforward consequence of Theorem 2.1.

Lemma 3.1.

With the above notation we have

1. $\overline{G}\cong{\hbox{\sf Z\kern-4.29993ptZ}}_{p^{m}}\times{\hbox{\sf Z\kern-4.29993ptZ}}_{p^{n}}$; and

2. $\overline{X}\cong C_{p^{m}}\times C_{p^{n}}$, for some $m,n\geq 1$.

Proof. By Theorem 2.1, the quotient group $G/\Phi(G)$ is elementary abelian, and so isomorphic to ${\hbox{\sf Z\kern-4.29993ptZ}}_{p}\times{\hbox{\sf Z\kern-4.29993ptZ}}_{p}$ since $d(G)=2$. Furthermore, $\Phi(G)=G^{\prime}G^{p}$. Hence $\overline{G}=G/G^{\prime}\cong{\hbox{\sf Z\kern-4.29993ptZ}}_{p^{m}}\times{\hbox{\sf Z\kern-4.29993ptZ}}_{p^{n}}$, for some $m,n\geq 1$. Part (ii) is then straighforward.  

We are now ready to show that $X$ has a particular local rigidity property, which forces a dihedral local action of its automorphism group $A$. More precisely, we prove the following result.

Theorem 3.2.

Let $G=\langle a,b\rangle$ be a $p$-group, $p$ an odd prime, let $X=\mathrm{Cay}(G,S)\neq K_{5}$, where $S=\{a^{\pm 1},b^{\pm 1}\})$, and let $A=\hbox{{\rm Aut}}(X)$. Then $E_{a}(X)$ and $E_{b}(X)$ are $A$-invariant, and for the induced action of $A_{1}$ on the neighbors’ set $N(1)$ we have

$$A_{1}^{N(1)}\leq D_{8}.$$

Proof. A quartic vertex-transitive graph of odd order which has an element of order $3$ in its vertex stabilizer, is necessarily $2$-arc-transitive, that is, the local action of its vertex stabilizer contains a copy of $A_{4}$. Therefore, it suffices to show that the stabilizer $A_{1}$ contains no element of order $3$.

If $d(G)=1$ and so $G$ cyclic then by [1, Theorem 1.1], a $2$-arc-transitive circulant of order $r$ is either $K_{r}$, $r>3$, $K_{r/2,r/2}$, $r>6$, $K_{r/2,r/2}-r/2K_{2}$, $r/2>5$ odd or $C_{r}$, $r>3$. Clearly, $K_{5}$ is the only quartic $2$-arc-transitive circulant.

We may therefore assume that $d(G)=2$. In order to establish non-existence of automorphisms of order $3$ we identify a feature that distinguishes monochromatic $2$-arcs from diverse $2$-arcs. This will force the edges of same color to be $A$-invariant which prevents the graph from being $2$-arc-transitive. We will show that diverse $2$-arcs cannot be contained in an odd cycle of smallest length.

A convenient way of looking at cycles in $X$ is by observing that every such cycle $C$ projects to a closed walk $\pi(C)=\overline{C}$ in $\overline{X}=\mathrm{Cay}(\overline{G},\overline{S})$. Since by Lemma 3.1 the latter is a grid, this puts a restriction on the number of appearances of each of the generators $a$ and $b$. We let $C(a)$, $C(a^{-1})$, $C(b)$ and $C(b^{-1})$, respectively, denote the numbers of appearances of $a$-arcs, $a^{-1}$-arcs, $b$-arcs and $b^{-1}$-arcs in the cycle $C$. We define the odd girth of $X$ to be the length of the shortest cycle of odd length in $X$, and any such cycle will be referred to as an odd girth cycle.

Let us first prove two auxiliary claims.

Claim 1 . For a cycle $C$ in $X$ the following hold:

1. $C(a)\equiv C(a^{-1})({\rm mod\,}p^{m})$, where $p^{m}$ is the order $|\overline{a}|$ of $\overline{a}$ in $\overline{G}$;

2. $C(b)\equiv C(b^{-1})({\rm mod\,}p^{n})$, where $p^{n}$ is the order $|\overline{b}|$ of $\overline{b}$ in $\overline{G}$;

Proof. Let $\overline{C}$ be the projection of $C$ in the grid $\overline{X}$./ Consider the trace of $\overline{C}$ on a $p^{m}$-gon $P_{m}$ by keeping only the appearances of $\overline{a}$ and its inverse in $\overline{C}$. This trace in $P_{m}$ is a closed walk represented by a sequence of length $C(a)+C(a^{-1})$ whose only items are $\overline{a}$ and/or its inverse. Note that in this sequence, we may replace $\overline{a}$ and its inverse, by $a$ and its inverse.

There are three cases to consider. Either this sequence consists of symbol $a$ only, of symbol $a^{-1}$ only, or there are consecutive symbols $aa^{-1}$ or $a^{-1}a$. In the first two cases we obviously have part (i). This holds because the sequence represents a closed walk in $P_{m}$, and we have either $C(a)=kp^{m}$ and $C(a^{-1})=0$ or $C(a)=0$ and $C(a^{-1})=kp^{m}$. In the third case we use induction on the number of adjacent appearances of $aa^{-1}$ or $a^{-1}a$. By cancelling any such appearance, we obtain a closed walk of length $C(a)-1+C(a^{-1})-1$. By induction $C(a)-1$ is congruent to $C(a^{-1})-1$ modulo $p^{m}$. The induction step follows since $p$ is odd. The same holds for the base of induction, that is, when there is a single appearence of such an adjacent pair. The reduction results in a closed walk as in the first two cases of length $C(a)-1+C(a^{-1})-1$. An analogous argument can be used for part (ii), concluding the proof of Claim 3.2. ∎

We next identify a feature that distinguishes monochromatic $2$-arcs from diverse $2$-arcs.

Claim 2 . No diverse $2$-arc is contained in an odd girth cycle of $X$.

Proof. With no loss of generality assume that $|\overline{a}|=m\leq n=|\overline{b}|$. Given an arbitrary cycle $C$ in $X$ containing a diverse $2$-arc, we have by Claim 3.2 that

$$C(a)=C(a^{-1})+kp^{m}\ {\rm and}\ C(b)=C(b^{-1})+lp^{n}.$$

for some $k,l\geq 0$. The length $|C|$ of $C$ is then equal to

$$C(a)+C(a^{-1})+C(b)+C(b^{-1})=2C(a^{-1})+2C(b^{-1})+kp^{m}+lp^{n}.$$

Assuming that $|C|$ is odd we must have that exactly one of $k$ or $l$ is odd. This shows that

$$|C|\geq 2C(a^{-1})+2C(b^{-1})+p^{m}$$

However $2C(a^{-1})+2C(b^{-1})>0$, for otherwise $C(a^{-1})=C(b^{-1})=0$ and hence $C(a)=kp^{m}$ and $C(b)=lp^{n}$. In either case $|C|>p^{m}$. ∎

Assume now that there exists $\alpha\in A_{1}^{N(1)}$ of order $3$. Then $\alpha$ fixes a neighbor of vertex $1$ and the other three neighbors are all in one orbit of $\langle\alpha\rangle$. We may assume that either $a$ or $b$ is fixed by $\alpha$. Suppose first that $\alpha(a)=a$. Then $Orb_{\langle\alpha\rangle}(a^{-1})=\{a^{-1},b,b^{-1}\}$. But this contradicts the fact that the $2$-arc $(a,1,a^{-1})$ is in an odd girth cycle of length $p^{m}$ whereas the $2$-arc $(a,1,b)$ is not (in view o Claim 3.2). Suppose now that $\alpha(b)=b$. Then $Orb_{\langle\alpha\rangle}(b^{-1})=\{a,a^{-1},b^{-1}\}$. Again, the $2$-arc $(a,1,a^{-1})$ is in an odd girth cycle of length $p^{m}$ whereas the $2$-arc $(a,1,b^{-1})$ is not (again by Claim 3.2). This proves that no element of order $3$ exists in $A_{1}$ and thus $A_{1}^{N(1)}\leq D_{8}$.  

The next two corollaries need no formal proofs.

Corollary 3.3.

Every connected quartic Cayley graph of a $p$–group, $p$ odd, other than $K_{5}$, admits a dihedral local action of its automorphism group.

Corollary 3.4.

No connected quartic Cayley graph of a $p$–group, $p$ odd, other than $K_{5}$, is $2$-arc-transitive.

4 A CFSG-free proof of Feng-Xu theorem

We start by making the following observation on normality of $X={\rm Cay}(G,S)$, where $X$ is as defined in (2).

Proposition 4.1.

Let $G$ be a $p$-group. The graph $X=\mathrm{Cay}(G,S)$, where $S=\{a^{\pm 1},b^{\pm 1}\}$, is normal if and ony if each of sets $\overrightarrow{E_{s}}$, $s\in S$ is $A$-invariant, where $A=\mathrm{Aut}(X)$.

Proof. Suppose first that $X$ is normal. Quotienting by the action of $G$ results in a regular covering projection of $X$ onto a $1$-vertex digraph with two oriented loops labelled by $a$ and $b$. Since $G$ is normal in $A$ it is generally known that $A$ projects along this covering. In other word, the sets $\overrightarrow{E_{s}}$, $s\in S$, are invariant under the action of $A$.

Conversely, if each of the four sets in ${\cal A}$ is invariant under the action of $A$, then $A$ projects and therefore $G$ must be normal in $A$.  

For more on covering projections we refer the reader to [22, 27]. We are now ready to give a CFSG-free proof of Feng-Xu theorem, a rewording of which is given below.

Theorem 4.2.

(Feng, Xu, 2005) Let $G=\langle a,b\rangle$ be a regular $p$-group, $p\neq 2,5$ a prime. Then $X=\mathrm{Cay}(G,S)$, where $S=\{a^{\pm 1},b^{\pm 1}\}$, is normal.

Proof. In the original proof [13] the authors refer to [2, Theorem 1.2] for the case when $G$ is abelian, and then proceed with the nonabelain case. In our approach, the distinction we make is on the minimum number of generators $d(G)$.

Suppose first that $d(G)=1$, and hence $G$ cyclic. Since $G$ is a $p$-group we may assume that $a$ is a generator of $G$. But then $E_{a}$ consists of a unique cycle. Take an arbitrary automorphism $\alpha\in A_{1}$. If $\alpha$ is color preserving, then $\alpha$ either preserves or reverses the orientation of this cycle, and so either $\alpha=1$ or $\alpha$ is a reflection swapping each $g\in G$ with its inverse. Hence $\alpha$ normalizes $G$, as desired. If $\alpha$ is color swapping, then $b$ is also a generator of $G$ and $E_{b}$ consists of a unique cycle too. Now $\alpha$ takes the unique $a$-cycle either to the unique $b$-cycle or to the unique $b^{-1}$-cycle. As a consequence, all of the sets $\overrightarrow{E_{s}}$, $s\in S$ are invariant under the action of $\alpha$ and so $G$ is normal in $A$, and hence $X$ is normal.

Suppose now that $d(G)=2$ and so $G$ is non-cyclic. Assume by contradiction that $X=\mathrm{Cay}(G,S)$, where $S=\{a,a^{-1},b,b^{-1}\}$, is a counterexample (to the statemnet of the theorem) of minimal order. Now, byTheorem 3.2, the stabilizer $A_{1}$ is a $2$-group. Hence $A$ is a $\{2,p\}$-group and thus solvable by Theorem 2.2.

Let $M\cong{\hbox{\sf Z\kern-4.29993ptZ}}_{p}^{k}$ be the minimal normal subgroup of $A$. Then the quotient graph

$$Y={\rm Cay}(G/M,\{aM,a^{-1}M,bM,b^{-1}M\},$$

cannot be quartic, for non-normality of $X$ carries over to $Y$, and in this case $X$ would not have been a minimal counterexample. It follows that $Y$, a graph of odd order, must then be of valency $2$ and so a cycle. Therefore $G/M$ is cyclic, and so $M$ must contain $G^{\prime}$ as a subgroup. Consequently, $G^{\prime}$ is elementary abelian. In particular,

$$(G^{\prime})^{p}=1.$$ (3)

Since $G$ is a regular $p$-group, by combining equations (1) and (3), we have

$$(ab)^{p}=a^{p}b^{p}.$$ (4)

As in the paragraph preceding Theorem 3.2, let $\pi:G\to\overline{G}=G/G^{\prime}$ be the natural projection. Consider the action of the quotient group $\overline{G}$ on the quotient graph $\overline{X}=\mathrm{Cay}(\overline{G},\overline{S})$. By Lemma 3.1,

$$\overline{X}\cong C_{p^{m}}\times C_{p^{n}},$$

for some $n\geq m\geq 1$. We will now analyze certain cycles in $X$ forced to exist by the above equation (4), and their closed walks projections in $\overline{X}$

But first an observation about normality violating automorphisms. Since $X$ is not normal it follows by Proposition 4.1 that there is an automorphism $\alpha\in A_{1}$ such that for some $s\in S$ the set $\overrightarrow{E_{s}}$ is not $\alpha$-invariant. We claim that a normality violating automorphism satisfies the following property in its action on alternating $3$-arcs.

Claim. If $X$ is not normal then it admits an automorphism mapping an $ab^{\pm 1}a-$arc or a $ba^{\pm 1}b-$arc to an $ab^{\pm 1}a^{-1}-$arc or a $ba^{\pm 1}b^{-1}-$arc.

Proof. Let $\alpha$ be a normality violating automorphism of $X$ and assume with no loss of generality that the set $\overrightarrow{E_{a}}$ is not an $\alpha$-invariant. (The argument below is analogous if it is the set $\overrightarrow{E_{b}}$ that is not an $\alpha$-invariant.)

Suppose first that $\alpha$ is color preserving. Then the set of all $a$-cycles splits into two subsets: the first consists of those cycles which under $\alpha$ preserve the orientation, while for the cycles in the second subset the orientation is reversed. But the graph $X$ is connected, and so there must exist two $a$-cycles, $C_{1}$ and $C_{2}$, joined by a $b$-edge and such that $\alpha$ preserves the orientation of $C_{1}$ but reverses that of $C_{2}$. This means that there is a vertex $u\in V(C_{1})$ such that $v=ub^{\pm 1}\in V(C_{2})$. By assumption $\alpha$ preserves the orientation of the arc $(ua^{-1},u)$ but reverses that of $(v,va)$, meaning that the $3$-arc $(ua^{-1},u,v,va)$ is taken to the $3$-arc $(\alpha(u)a^{-1},\alpha(u),\alpha(v),\alpha(v)a^{-1})$ (see Figure 1). In other words, $\alpha$ takes an $ab^{\pm 1}a-$arc to an $ab^{\pm 1}a^{-1}-$arc.

Figure 1: Local structure of two $a$-cycles $C_{1}$ and $C_{2}$ joined by a $b$-edge.

Suppose now that $\alpha$ is color swapping. Then the set of all $a$-cycles splits into two sets, with some of them being mapped by $\alpha$ to $b$-cycles and some to $b^{-1}$-cycles. Again, this means that there are $a$-cycles $C_{1}$ and $C_{2}$ joined by a $b$-edge and such that $\alpha(C_{1})$ is a $b$-cycle and $\alpha(C_{2})$ is a $b^{-1}$-cycle. This means that there are vertices $u\in C_{1}$ and $v\in C_{2}$ such that the $3$-arc $(ua^{-1},u,v,va)$ is taken to $(\alpha(u)b^{-1},\alpha(u),\alpha(v),\alpha(v)b^{-1})$. In other words, $\alpha$ takes an $ab^{\pm 1}a$-arc to a $ba^{\pm 1}b^{-1}$-arc, completing the proof of Claim. ∎

To complete the proof of Theorem 4.2 we now distinguish three different cases depending on the orders of elements $a$ and $b$.

Case 1. Both $a$ and $b$ are of order $p$.

Then (4) becomes $(ab)^{p}=1$ which gives us color alternating $2p$-cycles in $X$. Of course, any of the other three “mirror” relations $(a^{-1}b)^{p}$, $(ab^{-1})^{p}$, and $(a^{-1}b^{-1})^{p}$ also produces such cycles in $X$. There are no other color-alternating $2p$-cycles in $X$. Namely, in the setting of the grid $\overline{X}\cong C_{p}\times C_{p}$, every such cycle translates into a color-alternating closed walk of length $2p$. So let $C$ be an arbitrary color-alternating cycle of length $2p$ in $X$ and let $\overline{C}$ be the corresponding color-alternating closed walk in the grid $\overline{X}$. Since $a^{p}=1=b^{p}$, we have by Claim 3.2 in the proof of Theorem 3.2, that $C(s)\equiv C(s^{-1})({\rm mod\,}p)$, for $s\in\{a,b\}$. In view of the fact that $\overline{X}=C_{p}\times C_{p}$, it is then clear that such a cycle $C$ can only occur by using either $a$-arcs $p$ times or $a^{-1}$-arcs $p$ times, and analogously, using either $b$-arcs $p$ times or $b^{-1}$-arcs $p$ times. In other words, for a color-alternating cycle $C$ of length $2p$ in $X$ we have that

$$C(a)=p{\rm\ or}\ C(a^{-1})=p{\rm\ and\ }C(b)=p\ {\rm or}\ C(b^{-1})=p,$$ (5)

for in all other cases the congruences conditions in Claim 3.2 from the proof of Theorem 3.2 would be violated.

We now use the above Claim. Assuming with no loss of generality that $\overrightarrow{E_{a}}$ is not $\alpha$-invariant, we have that $\alpha$ takes an $ab{\pm}a$-arc to an $ab{\pm}a^{-1}$-arc or a $ba{\pm}b^{-1}$-arc. Either way, it takes a $3$-arc that is contained in a color-alternating cycle of length $2p$ to a $3$-arc that is not contained in such a cycle. This contradiction proves that this case is not possible.

Case 2. Precisely one of $a$ and $b$ has order $p$.

Then $a^{p}=1$ as by assumption $m\leq n$. Hence (4) becomes $(ab)^{p}=b^{p}$, and so

$$(ab)^{p-1}ab^{-p+1}=1.$$ (6)

This gives us a cycle $C$ of length $3p-2$ in $X$, asymmetric in $a$-edges and $b$-edges appearances. The normality violating automorphism $\alpha$ is therefore necessarily color preserving. Consequently, $C(a)=p$ and $C(b)=C(b^{-1})=p-1$ implies that

$$\alpha(C)(a)=p\ {\rm or}\ \alpha(C)(a^{-1})=p\ {\rm and}\ {\rm that}\ \alpha(C)(b)=\alpha(C)(b^{-1})=p-1.$$

Observe that in $X$ there must exist a $b^{-1}$-cycle, call it $B$, intersecting $C$ in a $b^{-p+1}$-arc. Now in view of Theorem 3.2, the image of $B\cap C$ under $\alpha$ is either a $b^{-p+1}$-arc or a $b^{p-1}$-arc. This implies that the complementary arc in $\alpha(C)$ must then arise, respectively, from one of the sequences $(a^{\pm 1}b)^{p-1}a^{\pm 1}$ or $(a^{\pm 1}b)^{-p+1}a^{\pm 1}$. In short, $\alpha(C)$ is a cycle that arises from the relation (6) or from one of its three mirror relations:

$$(ab^{-1})^{p-1}ab^{p-1},\,(a^{-1}b)^{p-1}a^{-1}b^{-p+1},\,(a^{-1}b^{-1})^{p-1}a^{-1}b^{p-1}.$$ (7)

Consequently, the normality violating automorphism $\alpha$ cannot take an $ab^{\pm 1}a$-arc or an $a^{-1}b^{\pm 1}a^{-1}$-arc to an $ab^{\pm 1}a^{-1}$-arc or to an $a^{-1}b^{\pm 1}a$-arc, contradicting the above Claim, and so disproving Case 2.

Case 3. None of $a$ and $b$ has order $p$.

In this case, (4) gives us a cycle $C$ of length $4p-4$ with the accompanying relation

$$(ba)^{p-1}b^{-p+1}a^{-p+1}=1.$$ (8)

Here, in view of $a$-edge versus $b$-edge symmetry, the automorphism $\alpha$ could be either color preserving or color swapping. But again an analogous argument to the one used in Case 2 (on the cycle $C$ intersecting with a $b^{-p+1}$-cycle $B$) we can deduce that the accompanying relation of the cycle $\alpha(C)$ must be either the same relation (8) or one of its three mirror relations $(ba^{-1})^{p-1}b^{-p+1}a^{p-1}=1$, $(b^{-1}a)^{p-1}b^{p-1}a^{-p+1}=1$ or $(b^{-1}a^{-1})^{p-1}b^{-p+1}a^{p-1}=1$. It follows then that $\alpha$ cannot take an $ab^{\pm 1}a$-arc or an $a^{-1}b^{\pm 1}a^{-1}$-arc to an $ab^{\pm 1}a^{-1}$-arc or to an $a^{-1}b^{\pm 1}a$-arc, (and the equivalent ones with roles of $a$ and $b$ swapped). This contradicts the above Claim, and takes care of Case 3 too, completing the proof of Theorem 4.2.  

Data availability: No datasets were used to support the findings of this article.