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 a special case 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, one of which is of order \(p\), 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\).
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 [8, 9, 23]).
A fairly good example of what we have in mind is the extensive knowledge that has been acquired 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 [27, 28]), 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 [6, 7] 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 [10, 11, 13, 18, 19, 22, 24, 25, 29, 30, 31]).
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 [20]), 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 \(\mathrm{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 [5, 17, 15, 14, 16] 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 [12]. 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=\mathrm{Cay}(G, S)\) be a connected tetravalent Cayley graph on \(G\). Then \(\mathrm{Aut}(\mathrm{Cay}(G, S))\) is the semidirect product of \(R(G)\) with \(\mathrm{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, \(\mathrm{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 \(\mathrm{Cay}(G, S)\) is the semidirect product of \(R(G)\) with \(\mathrm{Aut}(G, S)\) is precisely the definiton of the graph \(\mathrm{Cay}(G, S)\) being normal, that is, the group \(G\) being normal in \(\mathrm{Aut}(\mathrm{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’=[G,G]\) such that
\[(xy)^p = x^py^p c^p.\tag{1}\]
(For example, note that any \(p\)-group that is either abelian, or of exponent \(p\), or of nilpotency class less than \(p\), is necessarily 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 a special case of the above Feng-Xu theorem, with one of the generators of order \(p\), a proof that is essentially combinatorial in nature, save for a couple of group-theoretic tools.
Theorem 1.2. Let \(G= \langle a,b \rangle\) be a regular \(p\)-group, \(p \neq 2,5\) a prime, such that \(a\) is of order \(p\). Then \(X=\mathrm{Cay}(G,\{a^{\pm 1},b^{\pm 1}\})\) is normal.
We will prove Theorem 1.2 by first showing that in a quartic Cayley graph of an arbitrary \(p\)-group with a minimum generating set of two elements, one of which is of order \(p\), 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. 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 the proof of Theorem 1.2.
In this paper, all groups and graphs are assumed to be finite. By \(\mathbb{Z}_n\), \(n \geq2\), we denote the cyclic group of order \(n\), and by \(C_n\), \(n\geq3\), the cycle (the connected graph of valency \(2\)) of length \(n\). Given a graph \(X\), we let \(V(X)\), \(E(X)\), \(A(X)\) and \(\mathrm{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\). (In the literature the term block of \(G\) and \(g\in G\) is often used.)
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 [4]). If \(G\) is a finite \(p\)-group, then \[\Phi(G)=G’G^p,\] where \(G’ =[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 [2, 3]). 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=\mathrm{Cay}(G,S), \mathrm{where}\ \ S=\{a^{\pm1},b^{\pm1}\},\tag{2}\] be the corresponding connected undirected quartic Cayley graph, let \(A=\mathrm{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 equal to 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)\).
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 \mathbb{Z}_k\). A \(k\)-arc (of length \(k\)) of the form \((g,gs_0,gs_0s_1,\dots, gs_0s_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^{\pm1}b^{\pm1}\)-arcs and \(b^{\pm1}a^{\pm1}\)-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^{\pm1}\)-arcs, \(s \neq r, r^{-1}\). Such arcs are called alternating \(3\)-arcs, and are precisely: \(a^{\pm1}b^{\pm1}a^{\pm1}\)-arcs and \(b^{\pm1}a^{\pm1}b^{\pm1}\)-arcs.
As in the paragraph immediately after the statement of Theorem 2.2, we let \(G=\langle a,b\rangle\) be a \(p\)-group, \(p\) an odd prime, with an additional assumption that \(|a| = p\). Further, let \(\pi:G\to \overline{G} = G/G’\) be the natural projection. For \(g \in G\) we denote \(\overline{g} = gG’\). 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 straightforward consequence of Theorem 2.1.
Lemma 3.1. With the above notation and additionally \(d(G)=2\) we have
(i) \(\overline{G} \cong \mathbb{Z}_{p}\times \mathbb{Z}_{p^{n}}\); and
(ii) \(\overline{X} \cong C_{p}\times C_{p^{n}}\), for some \(n\ge 1\).
Proof. By Theorem 2.1, the quotient group \(G/\Phi(G)\) is elementary abelian, and so isomorphic to \(\mathbb{Z}_{p}\times \mathbb{Z}_{p}\) since \(d(G)=2\). Furthermore, \(\Phi(G) = G’ G^p\). Hence, since \(|a| =p\), we have \(\overline{G} = G/G’ \cong \mathbb{Z}_{p}\times \mathbb{Z}_{p^{n}}\), for some \(n\ge 1\). Part (ii) is then straightforward. \(\square\)
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, with \(a\) of order \(p\), let \(X=\mathrm{Cay}(G,S) \neq K_5\), where \(S=\{a^{\pm1},b^{\pm1}\}\), and let \(A=\mathrm{Aut}(X)\). Then \(A_1\) is a \(2\)-group.
Proof. Clearly, the stabilizer \(A_1\) contains no elements of prime order \(q >3\) for the restriction of \(A_1\) to the neighborhood \(N(1)\) is a permutation group of degree \(4\). Therefore it suffices to show that the stabilizer \(A_1\) contains no element of order \(3\); in other words, that \(A_1^{N(1)}\) does not contain a copy of \(A_4\) (and consequently the graph \(X\) is not \(2\)-arc transitive).
Suppose first that \(d(G) =1\), and so \(G\) is cyclic. 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/2 K_2\), \(r/2 > 5\) odd or \(C_r\), \(r > 3\). Clearly, among them \(K_5\) is the only quartic graph. But \(K_5\) is excluded from Theorem 3.2.
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:
(i) \(C(a) \equiv C(a^{-1}) (\mod p)\);
(ii) \(C(b) \equiv C(b^{-1}) (\mod p^n)\), where \(p^n =|\overline{b}|\) is the order of \(\overline{b}\) in \(\overline{G}\).
Proof. Let \(C\) be a cycle. Since \(G/G’\) is abelian, we have \(a^{C(a)-C(a^{-1})}G’ = b^{C(b^{-1})-C(b)}G’\). Suppose \(C(a)-C(a^{-1}) \not\equiv 0 \ (\mod p)\). Then \(C(a)-C(a^{-1})\) is coprime to \(p\) and so \(a \in b^iG’\), for some \(i\in\mathbb{Z}_{p^n}\). But this implies that \(\overline{G} =G/G’\) is cyclic, contradicting Lemma 3.1(i). It follows that \(C(a)-C(a^{-1}) \equiv 0 \ (\mod p)\) and since \(|a| = p\), we have \(b^{C(b^{-1})-C(b)}G’= G’\), implying \(C(b^{-1})-C(b) \equiv 0 \ (\mod p^n)\). Claim 1 follows. \(\square\)
We next identify a feature that distinguishes monochromatic \(2\)-arcs from diverse \(2\)-arcs.
Claim 2. The odd girth of \(X\) is \(p\) and no diverse \(2\)-arc is contained in an odd girth cycle of \(X\).
Proof. First, for an odd length cycle \(C\) we cannot simultaneously have \(C(a) = C(a^{-1})\) and \(C(b) = C(b^{-1})\). Consequently, Claim 1 implies that either \(|C(a) -C(a^{-1})| \geq p\) or \(|C(b) -C(b^{-1})| \geq p^n\) and so no cycle of odd length less than \(p\) exists. In addition, if \(C\) contains a diverse \(2\)-arc, then at least one of \(C(a)\) and \(C(a^{-1})\) is nonzero and also at least one of \(C(b)\) and \(C(b^{-1})\) is nonzero. This forces the length of \(C\) to be bigger than \(p\). \(\square\)
Suppose now that there exists \(\alpha\in A_1\) of order \(3\). Let \(F\) be the set of vertices fixed by \(\alpha\). Clearly, \(F\neq V(X)\). As \(X\) is connected, there are adjacent vertices \(h\in F\) and \(g\notin F\). Taking \(v=h\), the automorphism \(\alpha\) fixes \(v\) and acts nontrivially on \(N(v)\). Since \(\alpha\) has order \(3\) and \(|N(v)|=4\), the induced action on \(N(v)\) has cycle structure \((1)(3)\).
We may assume that either \(va\) or \(vb\) is fixed by \(\alpha\). Suppose first that \(\alpha(va)=va\). Then \(Orb_{\langle\alpha\rangle}(va^{-1})=\{va^{-1}, vb, vb^{-1}\}\). But this contradicts the fact that the \(2\)-arc \((va, v, va^{-1})\) is in an odd girth cycle of length \(p\) whereas the \(2\)-arc \((va, v, vb)\) is not (in view of Claim 2). Suppose now that \(vb\) is fixed. Then \(\{va,va^{-1},vb^{-1}\}\) is a \(3\)-orbit. Hence some power of \(\alpha\) maps the monochromatic \(2\)-arc \((va,v,va^{-1})\) to a diverse \(2\)-arc, again contradicting Claim 2. This proves that no element of order \(3\) exists in \(A_1\) and so \(A_1\) is a \(2\)-group. \(\square\)
The next two corollaries to Theorem 3.2 need no formal proofs.
Corollary 3.3. Let \(p\) be an odd prime and let \(G =\langle a,b \rangle\) be \(p\)-group with \(a\) of order \(p\). Then the quartic Cayley graph \(\mathrm{Cay}(G,\{a^{\pm1},b^{\pm1}\}) \neq K_5\), admits a \(D_8\) local action of its automorphism group.
Corollary 3.4. Let \(p\) be an odd prime and let \(G =\langle a,b \rangle\) be \(p\)-group with \(a\) of order \(p\). Then the quartic Cayley graph \(\mathrm{Cay}(G,\{a^{\pm1},b^{\pm1}\}) \neq K_5\), is not \(2\)-arc-transitive.
Let \(G =\langle a,b \rangle\) be an arbitrary \(p\)-group, and \(S =\{ a^{\pm1},b^{\pm1}\}\). We start by making the following observation on normality of \(X = \mathrm{Cay} (G,S)\).
Proposition 4.1. Let \(G =\langle a,b \rangle\) be a \(p\)-group. The graph \(X = \mathrm{Cay}(G,S)\), where \(S=\{a^{\pm1},b^{\pm1}\}\), is normal if and only if \(A =\mathrm{Aut}(X)\) preserves the partition \(\{\overrightarrow{E_{s}} \ | \ s \in S\}\).
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 a common knowledge that \(A\) projects along this covering. In other words, the sets \(\overrightarrow{E_{s}}\), \(s \in S\), are invariant under the action of \(A\).
Conversely, if each of the four sets in \(\{\overrightarrow{E_{s}} \ | \ s \in S\}\) is invariant under the action of \(A\), then \(A\) projects and therefore \(G\) must be normal in \(A\). \(\square\)
For more on covering projections we refer the reader to [21, 26].
We are now ready to give a CFSG-free proof of Theorem 1.2.
Proof of Theorem 1.2. Note that \(p \neq 2,5\). Let \(A=\mathrm{Aut}(X)\). Suppose first that \(d(G) =1\), and hence \(G\) cyclic. Since \(G\) is a \(p\)-group and \(|a|=p \leq p^n =|b|\), we may assume that \(b\) is a generator of \(G\). But then \(E_b\) 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 of order \(p\). Hence \(a\) is also a generator of \(G\) and \(E_a\) consists of a unique cycle too. (In fact, in this case \(X\) is a \(p\)-circulant.) Now \(\alpha\) takes the unique \(b\)-cycle either to the unique \(a\)-cycle or to the unique \(a^{-1}\)-cycle. As a consequence, \(\langle \alpha\rangle\) and hence \(A\) preserves the partition \(\{\overrightarrow{E_{s}} \ | \ s \in S\}\). By Proposition 4.1, \(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)\), is a counterexample (to the statement of the theorem) of minimal order. Now, by Theorem 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\) be a minimal normal subgroup of \(A\). If \(M\) is a \(2\)-group, it must be contained in a vertex stabilizer. But then its normality implies that it is contained in every vertex stabilizer, and hence it acts trivially. This contradiction implies that \(M \cong \mathbb{Z}_p^k\) for some \(k\). As \(M\) is minimal normal subgroup of \(A\) it is contained in every Sylow \(p\)-subgroup of \(A\), and so it contained in \(G\).
Consider the quotient graph \[Y = \mathrm{Cay}(G/M, \{aM,a^{-1}M,bM,b^{-1}M\}.\]
It cannot be quartic for non-normality of \(X\) carries over to \(Y\), and in this case \(X\) would not have been a minimal counterexample. Namely, if \(Y\) was quartic, then by minimality of \(X\), we would have that \(G/M\) is normal in \(A/M\). But then \(G\) would be normal in \(A\), a contradiction. It follows that \(Y\), a graph of odd order, must then be of valency \(2\) and so a cycle of odd length. Therefore \(G/M\) is cyclic, and so \(M\) must contain \(G’\) as a subgroup. Consequently, \(G’\) is elementary abelian. In particular,
\[(G’)^p = 1.\tag{3}\]
Since \(G\) is a regular \(p\)-group, it follows by (1) that \((ab)^p = a^pb^p c^p\) for some \(c \in G’\) and so (3) implies that
\[(ab)^p = a^pb^p.\tag{4}\]
As in the paragraph preceding Lemma 3.1, let \(\pi:G\to \overline{G} = G/G’\) 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}\times C_{p^{n}},\] for some \(n\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. 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^{\pm1}a-\)arc or \(ba^{\pm1}b-\)arc to an \(ab^{\pm1}a^{-1}-\)arc or \(ba^{\pm1}b^{-1}-\)arc.
Proof. Let \(\alpha\) be a normality violating automorphism of \(X\).
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^{\pm1} \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^{\pm1}a-\)arc to an \(ab^{\pm1}a^{-1}-\)arc.
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^{\pm1}a\)-arc to a \(ba^{\pm1}b^{-1}\)-arc, completing the proof of Claim. \(\square\)
To complete the proof of Theorem 1.2 we now distinguish two different cases depending on whether the order of \(b\) is also \(p\) or not.
Case 1. \(|b| =p\).
Then (4) becomes \((ab)^p =1\) which, since \(p\) is a prime, 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 \(2p\)-cycle in \(X\) projects 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 1 in the proof of Theorem 3.2, that \(C(s) \equiv C(s^{-1}) (\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,\tag{5}\] for in all other cases the congruence conditions in Claim 1 from the proof of Theorem 3.2 would be violated.
We now use the above Claim. Assuming with no loss of generality that \(\alpha\) takes an \(ab^{\pm1}a\)-arc to an \(ab^{\pm1}a^{-1}\)-arc or \(ba^{\pm1}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. \(|b| = p^n \neq p\).
Then equality (4) becomes \((ab)^p = b^p\), and so \[(ab)^{p-1}ab^{-p+1} = 1.\tag{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\) impliy that \[\alpha(C)(a)=p \ {\rm or} \ \alpha(C)(a^{-1})=p \ {\rm and} \ \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^{\pm1}b)^{p-1}a^{\pm1}\) or \((a^{\pm1}b)^{-p+1}a^{\pm1}\). 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}.\tag{7}\]
Consequently, the normality violating automorphism \(\alpha\) cannot take an \(ab^{\pm1}a\)-arc or an \(a^{-1}b^{\pm1}a^{-1}\)-arc to an \(ab^{\pm1}a^{-1}\)-arc or to an \(a^{-1}b^{\pm1}a\)-arc, contradicting the above Claim, and so disproving Case 2 too, completing the proof of Theorem 1.2. \(\square\)
Recall that \(p\)-groups of exponent \(p\), that is groups with all non-trivial elements of order \(p\), form a subclass of regular \(p\)-groups, and so the proof of the corollary below is straightforward.
Corollary 4.2. Let \(p \neq 2, 5\) be a prime and let \(G=\langle a,b \rangle\) be a \(p\)-group of exponent \(p\). Then the quartic Cayley graph \(\mathrm{Cay}(G,\{a^{\pm1},b^{\pm1})\) is normal.
The authors declare no conflicts of interest.
This research received no external funding.
This study is theoretical and does not involve the generation or analysis of datasets.
All the authors contributed equally. All authors have read and agreed to the published version of the manuscript.