Automorphism groups of the constituent graphs of integral distance graphs

Abstract

In this paper, we consider the automorphism groups of Cayley graphs which are a basis of a complete Boolean algebra of strongly regular graphs, one of such graph is the integral distance graph $\Gamma .$ The automorphism groups of the integral distance graphs Γ were determined by Kovács and Ruff in 2014 and by Kurz in 2009. Our point of interest will be restricted to the one determined by Kovács and Ruff. Here we consider the automorphism groups of subgraphs ${\Gamma }_1$ and ${\Gamma }_2,$ which inherit the properties of $\Gamma .$ It will be shown that $\text{Aut} \Gamma$ is isomorphic to $\text{Aut} {\Gamma }_2$ and that $\text{Aut} {\Gamma }_1$ is isomorphic to $S_{{\mathbb{F}}_q^2}\wr S_{[2]}.$

KEYWORDS:

• Automorphism groups
• integral distance graphs
• Boolean algebra of Cayley sets

1 Introduction

In this paper, all considered graphs are assumed to be finite, simple and connected. A graph $\Gamma =(V,E)$ is a set V of vertices together with a relation E, which is irreflexive and symmetric. If in $\Gamma =(V,E)$, the reflexivity and symmetry of the binary relation are not insisted upon, then we speak of a directed graph or digraph. For a graph Γ, we let $V(\Gamma )$, $E(\Gamma )$ and {x, y} denote the vertex set, the edge set, and an edge with endpoints x and y in $V(\Gamma )$, respectively. For an edge {x, y}, x and y are said to be adjacent in $\Gamma .$ For digraphs, arcs are represented by pairs of the form $(u,v).$ By the complement of Γ is meant a graph ${\Gamma }^C$ with $V({\Gamma }^C)=V(\Gamma )$ such that $\{x,y\}\in E({\Gamma }^C)$ if and only if $\{x,y\}\notin E(\Gamma ).$

Let Γ and Λ be graphs. By a graph isomorphism between Γ and Λ is meant a bijection $\sigma :V(\Gamma )\to V(\Lambda )$ such that $\{x^{\sigma },y^{\sigma }\}\in E(\Lambda )$ if and only if $\{x,y\}\in E(\Gamma )$ and if Γ is isomorphic to Λ, it is denoted by $\Gamma \cong \Lambda .$ By a self-complementary graph is meant a graph Γ isomorphic to its complement. If σ is a permutation of $V(\Gamma )$ that preserves adjacency relations, then it is called an automorphism of $\Gamma .$ By the automorphism group of Γ, denoted by $\text{Aut} \Gamma$, is meant the set of all automorphisms of $\Gamma .$ Γ is vertex-transitive if $\text{Aut} \Gamma$ is transitive on $V(\Gamma );$ i.e., $V(\Gamma )$ is a single orbit under the action of $\text{Aut} \Gamma .$

Let G be a group and $1_G$ an identity element of G. Let S be a subset of G such that $1_G\notin S$ and $S=S^{-1}.$ By the Cayley graph $\Gamma =\text{Cay}(G,S)$ is meant a graph defined by $V(\Gamma ):=G$ and $E(\Gamma ):=\left\{\right\{x,xs\}:x\in G,s\in S\}.$ The set S is called a Cayley set on G. It is a classical result that for $\Gamma =\text{Cay}(G,S)$, the subset $G\setminus (S\cup \{1_G\})$ is a Cayley set on G for the complementary graph ${\Gamma }^C.$ The mapping defined by $x\mapsto gx,x,g\in G$, is clearly an automorphism of $\Gamma =\text{Cay}(G,S).$ It is immediate therefore that, $\Gamma =\text{Cay}(G,S)$ is vertex-transitive. The following result regarding isomorphism of Cayley graphs is very important and will be used in the last section of the paper.

Proposition 1.

[3, Lemma 3.7.3] Let $\varphi$ be an automorphism of the group G and let S be a Cayley set of G. Then $\text{Cay}(G,S)\cong \text{Cay}(G,S^{\varphi }).$

In addition to the pertinent concepts of graphs to be used in this paper, we present some definitions and results related to primitive permutation groups and integral distances over finite fields.

The action of a group G on the set Ω can be extended to subsets Δ of Ω by defining ${\Delta }^x=\{{\delta }^x:\delta \in \Delta \}$ for each $\Delta \subseteq \Omega$ and $x\in G.$ Denote by $G_{\Delta }$ the elementwise stabilizer of Δ in G; while $G_{\{\Delta \}}$ denotes the setwise stabilizer of Δ in G. If $\Delta =\{{\delta }_1,\dots ,{\delta }_k\}$, then $G_{{\delta }_1,\dots ,{\delta }_k}$ denotes $G_{\{{\delta }_1,\dots ,{\delta }_k\}}$; in particular, $G_{\delta }$ denotes $G_{\left\{\delta \right\}}.$ If in addition, G acts transitively on Ω, a subset $\Delta \subseteq \Omega$ is called a block for G if for every $x\in G,{\Delta }^x=\Delta$ or $\Delta \cap {\Delta }^x=\varnothing .$ The sets ${\Delta }^x,x\in G$, form a partition of Ω which is called a system of blocks for G containing $\Delta .$ If G is transitive on Ω, then it is clear that Ω and the singletons $\left\{\alpha \right\}$ ($\alpha \in \Omega$) are blocks for G. If the latter are the only blocks for G, then G is said to be primitive. Otherwise, G is called imprimitive.

It has been shown that a transitive permutation group G on Ω can be seen to act as a group of automorphisms of a directed graph. If G is finite, then G acts on $\Omega \times \Omega$ coordinatewise, and the respective orbits are called the orbitals of G. Since G is transitive on Ω, the set $\{(\omega ,\omega ):\omega \in \Omega \}$ is an orbital, explicitly called the diagonal orbital of G. Given an orbital Δ of G, the orbital digraph $\text{Graph}(\Delta )$ is defined to have vertex set Ω and arc set $\Delta .$ The number of orbits of the stabilizer $G_{\omega }$ is equal to the number of the orbitals of G for any $\omega \in \Omega .$ This number is called the rank of G.

The purpose of this paper is to present what we consider as the building blocks of the two-dimensional integral distance graphs ${\mathfrak{G}}_{2,q}$ over the finite field ${\mathbb{F}}_q,$ $q=p^r,$ p prime and $p>2,$ and discuss their automorphism group. We will consider the action of automorphism groups of integral distance graphs in relation to the automorphisms of their constituent graphs.

In the rest of the paper, before we discuss the main results, we give in Section 2 some details of the automorphism groups of ${\mathfrak{G}}_{2,q}$ for $q\equiv 1\hspace{1em}(\mathrm{mod}4)$ to be used in Section 3.2. We shall look at the automorphism groups of the constituent graphs ${\Gamma }_i=\text{Cay}({\mathbb{F}}_q^2,S_i)$, i = 1, 2, 3, of ${\mathfrak{G}}_{2,q}$, $q\equiv 1\hspace{1em}(\mathrm{mod}4)$, with S_i, i = 1, 2, the two base subsets of ${\mathbb{F}}_q^2$ to be defined in Section 3, and $S_3={\mathbb{F}}_q^2\setminus (S_1\cup S_2\cup \{\mathbf{0}\}).$ In particular, we show that the automorphism group of the one of Γ_i, i = 1, 2, 3, is isomorphic to the direct product of the group of translations by the elements of ${\mathbb{F}}_q^2$ with the wreath product of the symmetric group $S_{[q-1]}$ by $S_{[2]}$ in Section 3.1, and the automorphism groups of the rest of the Γ_i s, i = 2, 3, are isomorphic to the automorphism group of the original graph ${\mathfrak{G}}_{2,q}$ in Section 3.2.

2 Integral automorphism of affine planes over finite fields

Two points in an Euclidean space are said to be at integral distance if their squared Euclidean distance is a perfect square. Integral point sets were defined in m-dimensional Euclidean space ${\mathbb{E}}^m$ as a set of points with pairwise integral distances in the Euclidean metric; see [5, 6, 8–10]. Here we consider such a concept to inner product spaces ${\mathbb{F}}_q^m$ over a finite field ${\mathbb{F}}_q,q=p^r$, p prime.

It turns out that it is useful to model integral point sets as cliques of certain graphs. For a given prime power $q=p^r$ and a given dimension, a graph of integral distance is a graph ${\mathfrak{G}}_{m,q}$ with vertex set ${\mathbb{F}}_q^m$, where two vertices $\mathbf{x}$ and $\mathbf{y}$ form an edge in it, if they are at integral distance. In [4], integral distance graphs ${\mathfrak{G}}_{m,q}$ were shown to be Cayley and strongly regular for $m\equiv 0\hspace{1em}(\mathrm{mod}2)$ as well as their constituent graphs for m = 2 and $q\equiv 1\hspace{1em}(\mathrm{mod}4)$ that we shall define in Section 3. The automorphism groups of ${\mathfrak{G}}_{m,q},$ $m\ge 2,$ have been described by Kovács et al. [7] and by Kurz et al. [6, 9, 10]. For $q\equiv 3\hspace{1em}(\mathrm{mod}4)$, the graph ${\mathfrak{G}}_{2,q}$ can be shown to be isomorphic to the Paley graph $P(q^2)$ of square order; see [6, 7, 10]. Our point of interest for symmetries will only focus on the two-dimensional case for $q\equiv 1\hspace{1em}(\mathrm{mod}4).$ Here, we shall only deal with automorphism groups of the constituent graphs of ${\mathfrak{G}}_{2,q}.$

For the finite field ${\mathbb{F}}_q$ of order $q=p^r$, p prime, ${\square }_q$ denotes the set of all perfect squares in ${\mathbb{F}}_q$ including the zero element. The norm $N:{\mathbb{F}}_q^2\to {\mathbb{F}}_q$ of a point $\mathbf{x}=(x_1,x_2)$ is defined by $N(\mathbf{x})=x_1^2+x_2^2$, and two points $\mathbf{x},\mathbf{y}\in {\mathbb{F}}_q^2$ are said to be at integral distance if $N(\mathbf{x}-\mathbf{y})\in {\square }_q.$ That is, the norm $N(\mathbf{x}-\mathbf{y})$ can be interpreted on the squared Euclidean distance between $\mathbf{x}$ and $\mathbf{y}.$ For a line $\mathbf{L}=\mathbf{P}+{\mathbb{F}}_q·\mathbf{Q}$ with $\{\mathbf{P},\mathbf{Q}\}\subset {\mathbb{F}}_q^2,\mathbf{Q}\ne (0,0),\mathbf{D}={\mathbb{F}}_q·\mathbf{Q}$ is called the direction of $\mathbf{L}.$ If $N(\mathbf{Q})\in {\square }_q$, then $\mathbf{D}$ is an integral direction. If $N(\mathbf{Q})=0$, then $\mathbf{D}$ is a vanishing direction.

In the finite field ${\mathbb{F}}_q$, it is shown in [2] that $-1\in {\square }_q$ for $q\equiv 1\hspace{1em}(\mathrm{mod}4).$ However, for $q\equiv 3\hspace{1em}(\mathrm{mod}4),-1\notin {\square }_q$ so that $x^2+1$ is irreducible. Here, ${\mathbb{F}}_q^2$ can be considered as ${\mathbb{F}}_q[i]$ where i is a root of the polynomial $x^2+1\in {\mathbb{F}}_q[x].$ In addition, ${\mathbb{F}}_q[i]$ can be identified as ${\mathbb{F}}_{q^2}$ which is a field, see [6, 7, 9].

The following parametric representation of pairs of ${\mathbb{F}}_q^2$ is very important. It will be a very useful result in some of the counting arguments in the rest of the paper.

Theorem 1.

[6, 10] Let $c\in {\mathbb{F}}_q$ and denote $P_c=\{(a,b,c)\in {\mathbb{F}}_q^3:a^2+b^2=c^2\}$ for $c\ne 0.$ Then $$P_0=\{\begin{array}{cc}\{(t,\pm t\omega ,0):t\in {\mathbb{F}}_q\}\hfill & \text{if }q\equiv 1\hspace{1em}\left(\mathrm{mod}4\right),\hfill \\ \{(0,0,0)\}\hfill & \text{if }q\equiv 3\hspace{1em}\left(\mathrm{mod}4\right);\hfill \end{array}$$ $$\mathit{and} P_c=\{(\pm c,0,c)\}\cup \{(0,\pm c,c)\}\cup \{\left(\frac{t^2-1}{t^2+1}·c,\frac{2t}{t^2+1}·c,c\right):t\in {\mathbb{F}}_q^{*},t^2\ne \pm 1\}.$$

Moreover, $$\begin{array}{c}\left|P_0\right|=\{\begin{array}{cc}2q-1\hfill & \text{if }q\equiv 1\hspace{1em}\left(\mathrm{mod}4\right),\hfill \\ 1\hfill & \text{if }q\equiv 3\hspace{1em}\left(\mathrm{mod}4\right);\hfill \end{array} \mathit{and}\\ \left|P_c\right|=\{\begin{array}{cc}q-1\hfill & \text{if }q\equiv 1\hspace{1em}\left(\mathrm{mod}4\right),\hfill \\ q+1\hfill & \text{if }q\equiv 3\hspace{1em}\left(\mathrm{mod}4\right).\hfill \end{array}\end{array}$$

For $q\equiv 1\hspace{1em}(\mathrm{mod}4)$, the points $\mathbf{P}\in {\mathbb{F}}_q^2$ can be represented in another basis of ${\mathbb{F}}_q^2$ that yields a simple representation of the norm and the vanishing lines. These points are said to be given in hyperbolic coordinates. In this representation, the coordinates $(\alpha ,\beta )$ in which the norm of $\mathbf{P}$ in that new basis is $N(\mathbf{P})=\alpha \beta$ with vanishing directions $({\mathbb{F}}_q,0)$ and $(0,{\mathbb{F}}_q).$ See further details in [6].

As with all combinatorial structures, the question of the automorphisms of integral point sets arises. In this case, there are two natural ways to define an automorphism: By an integral automorphism of the affine plane ${\mathbb{F}}_q^2$ is meant a permutation σ of ${\mathbb{F}}_q^2$ which preserves the integral distances; i.e., for all $\mathbf{x},\mathbf{y}\in {\mathbb{F}}_q^2$, $$N(\mathit{x}-\mathit{y})\in {\square }_q\iff N({\mathit{x}}^{\sigma }-{\mathit{y}}^{\sigma })\in {\square }_q.$$

If additionally the permutation σ is an element of the affine semi-linear group $\mathrm{A}\Gamma {\mathrm{L}}_2({\mathbb{F}}_q)$, then σ is called an affine integral automorphism.

The group of all integral automorphisms and those of all affine integral automorphisms are denoted by $\text{Aut}({\mathbb{F}}_q^2)$ and $\text{AffAut}({\mathbb{F}}_q^2)$, respectively. $\text{Aut}({\mathbb{F}}_q^2)$ is exactly the automorphism group of the graph of integral distances ${\mathfrak{G}}_{2,q}.$ It is clear that $\text{AffAut}({\mathbb{F}}_q^2)$ is a subgroup of $\text{Aut}({\mathbb{F}}_q^2)$ [6]. Now the following are the characterizations of the affine integral automorphisms of ${\mathbb{F}}_q^2.$

Theorem 2.

[6, 9] Let $q\notin \{5,9\}.$ Then $\text{AffAut}({\mathbb{F}}_q^2)$ is generated by

1. the translations ${\lambda }_{\mathbf{u}}:\mathbf{x}\mapsto \mathbf{x}+\mathbf{u}$ for all $\mathbf{u}\in {\mathbb{F}}_q^2$;

2. the reflexion $R:(x_1,x_2)\mapsto (x_2,x_1)$;

3. the spiral collineations $M:(x_1,x_2)\mapsto (x_1,x_2)(\begin{array}{cc}a& b\\ -b& a\end{array})$ for $a,b\in {\mathbb{F}}_q$ with $a^2+b^2\in {\square }_q^{*}$; and,

4. The Frobenius automorphisms $\sigma :(x_1,x_2)\mapsto (x_1^p,x_2^p)$, with p the characteristic of ${\mathbb{F}}_q.$

In [9], it has been shown that no other permutation of ${\mathbb{F}}_q^2$ than those mentioned above is an affine integral automorphism of ${\mathbb{F}}_q^2.$ Now in Theorem 2, with counting arguments, the orders of $〈R〉,$ $〈\sigma 〉$ and $〈{\lambda }_{\mathbf{u}}〉,$ $\mathbf{u}\in {\mathbb{F}}_q^2,$ are 2, r and $q^2,$ respectively. With the same argument, since ${\square }_q^{*}={\square }_q\setminus \left\{0\right\}$ is a subgroup of ${\mathbb{F}}_q^{*},$a multiplicative cyclic group, we have that $\left|{\square }_q^{*}\right|=\frac{q-1}{2}.$ Hence, with the help of Theorem 1 for the order of $〈M〉,$ it follows that $$|\text{AffAut}({\mathbb{F}}_q^2)|=\{\begin{array}{cc}{q}^2{(q-1)}^{2}r\hfill & \text{if }q\equiv 1\hspace{1em}\left(\mathrm{mod}4\right);\hfill \\ \hfill & q\notin \{5,9\};\hfill \\ q^2(q+1)(q-1)r\hfill & \text{if }q\equiv 3\hspace{1em}\left(\mathrm{mod}4\right).\hfill \end{array}$$

The details of automorphism groups of ${\mathfrak{G}}_{2,q}$ for $q\equiv 3\hspace{1em}(\mathrm{mod}4)$ were given in [9]. In either that case or $q\ne 5,$ q prime, it has been shown in [6, Theorem 9] that $\text{AffAut}({\mathbb{F}}_q^2)=\text{Aut}({\mathbb{F}}_q^2).$ In the remaining case; namely, $q\equiv 1\hspace{1em}(\mathrm{mod}4),$ $q=p^r$ and $r\ge 2,$ the map $\psi :(\alpha ,\beta )\mapsto (\alpha ,{\beta }^p)$ was shown to be an integral automorphism of ${\mathbb{F}}_q^2,$ but not an affine automorphism, so that $\text{AffAut}({\mathbb{F}}_q^2)$ and $\text{Aut}({\mathbb{F}}_q^2)$ are not isomorphic, see [6, Theorem 13]. In the latter case with $q\ne 9,$ it was conjectured in [6] that $\text{Aut}({\mathbb{F}}_q^2)=〈\text{AffAut}({\mathbb{F}}_q^2),\psi 〉.$ Hence this lead to the following.

Theorem 3.

[7, Theorem 1] Let $q=p^r$, where p is a prime and $q\equiv 1\hspace{1em}(\mathrm{mod}4),q\notin \{5,9\}.$ Then $|\text{Aut}({\mathbb{F}}_q^2)|={(q(q-1)r)}^2.$

3 Automorphism groups of the constituent graphs of ${\mathfrak{G}}_{2,q},$ $q\equiv 1\hspace{1em}(\mathrm{mod}4)$

By [4, Proposition 3.10], it is shown that ${\mathfrak{G}}_{2,q}$ is a Cayley graph $\text{Cay}({\mathbb{F}}_q^2,\mathbb{S})$ where $\mathbb{S}=\{\mathbf{x}\in {\mathbb{F}}_q^2:\mathbf{x}\ne (0,0),N(\mathbf{x})\in {\square }_q\}$ is the connecting set of the integral distance graph.

For $q\equiv 1\hspace{1em}(\mathrm{mod}4)$, there exists $\omega \in {\mathbb{F}}_q$ such that ${\omega }^2=-1.$ The linear mapping $\varphi :(x_1,x_2)\mapsto (x_1+\omega x_2,x_1-\omega x_2)$ defined in [7] maps the graph $\text{Cay}({\mathbb{F}}_q^2,\mathbb{S})$ to $\text{Cay}({\mathbb{F}}_q^2,{\mathbb{S}}^{\varphi })$ where ${\mathbb{S}}^{\varphi }=\{\mathbf{x}\in {\mathbb{F}}_q^2:\mathbf{x}(x_1,x_2)\ne \mathbf{0},x_1{x}_2\in {\square }_q\}$; i.e., $\varphi$ is a switch to hyperbolic coordinates, see [7].

We set $S:={\mathbb{S}}^{\varphi }$ and $\Gamma :=\text{Cay}({\mathbb{F}}_q^2,S).$ Here we consider the two base subsets S₁ and S₂ of ${\mathbb{F}}_q^2$ defined by (1) $$S_1=\{(x_1,x_2)\in {\mathbb{F}}_q^2\setminus \{(0,0)\}:x_1{x}_2=0\}=({\mathbb{F}}_q^{*},0)\cup (0,{\mathbb{F}}_q^{*});$$(1) and (2) $$S_2=\{(x_1,x_2)\in {\mathbb{F}}_q^2:x_1{x}_2\in {\square }_q^{*}\}.$$(2)

Clearly, $S=S_1\cup S_2.$ It is easy to show that S_i, i = 1, 2, are Cayley sets in the addition group ${\mathbb{F}}_q^2$ so that we have the Cayley graphs ${\Gamma }_i=\text{Cay}({\mathbb{F}}_q^2,S_i)$ by [4, Lemma 3.2, Corollary 3.3]. It is also shown in [4, 11] that the subsets S_i, i = 1, 2, of ${\mathbb{F}}_q^2$ form a basis of Boolean algebra $\mathfrak{B}=〈S_1,S_2〉$ of Cayley sets so that $\Gamma =\text{Cay}({\mathbb{F}}_q^2,S)$ is a Cayley graph by [4, Corollary 3.3]. In addition, we shall consider another subset (3) $$S_3={\mathbb{F}}_q^2\setminus (S_1\cup S_2\cup \{\mathbf{0}\})$$(3) so that we have another Cayley graph ${\Gamma }_3=\text{Cay}({\mathbb{F}}_q^2,S_3)$ by [4, Corollary 3.3]. The three graphs ${\Gamma }_i=\text{Cay}({\mathbb{F}}_q^2,S_i)$, i = 1, 2, 3, are called in this paper the constituent graphs of the integral distance graphs over ${\mathbb{F}}_q^2,q\equiv 1\hspace{1em}(\mathrm{mod}4).$

As a starting point, the following permutations of ${\mathbb{F}}_q^2$ have already been defined in [7]. $${\lambda }_{(a,b)}:(x_1,x_2)\mapsto (x_1+a,x_1+b),a,b\in {\mathbb{F}}_q,$$ $$R:(x_1,x_2)\mapsto (x_2,x_1),$$ $$M_a^{+}:(x_1,x_2)\mapsto (a{x}_1,a{x}_2),a\in {\mathbb{F}}_q^{*},$$ $$M_a^{-}:(x_1,x_2)\mapsto (a{x}_1,a^{-1}{x}_2),a\in {\mathbb{F}}_q^{*},$$ $$A_1:(x_1,x_2)\mapsto (x_1^p,x_2),\text{and}{A}_2:(x_1,x_2)\mapsto (x_1,x_2^p).$$

Let F be the group generated by the permutations of ${\mathbb{F}}_q^2$ defined above. We shall show that F is a subgroup of $\text{Aut} {\Gamma }_i$, where ${\Gamma }_i=\text{Cay}({\mathbb{F}}_q^2,S_i)$, i = 1, 2, 3, with S₁ and S₂ the base subsets of ${\mathbb{F}}_q^2$ defined above; and S₃ the complement of $S\cup \left\{\mathbf{0}\right\}$ in ${\mathbb{F}}_q^2,S=S_1\cup S_2.$

In addition, it is easy to show that F is also generated by the conjugates of the elements of $\text{AffAut}({\mathbb{F}}_q^2)$ from Theorem 2 by the ${\mathbb{F}}_q$ -linear mapping $\varphi :(x_1,x_2)\mapsto (x_1+\omega x_2,x_1-\omega x_2)$, ${\omega }^2=-1$, together with the mapping ψ defined in Section 2.

Moreover, it is shown that F in its action on $V({\Gamma }_i)$, i = 1, 2, 3, is primitive, see Lemma 2. That is, $\text{Aut} {\Gamma }_i$, i = 1, 2, 3, is therefore primitive.

We first show that F is a subgroup of $\text{Aut} {\Gamma }_i,i=1,2,3.$

Lemma 1.

Let S₁, S₂ and S₃ be defined as in Equations (1)(1) $$S_1=\{(x_1,x_2)\in {\mathbb{F}}_q^2\setminus \{(0,0)\}:x_1{x}_2=0\}=({\mathbb{F}}_q^{*},0)\cup (0,{\mathbb{F}}_q^{*});$$(1) , (2)(2) $$S_2=\{(x_1,x_2)\in {\mathbb{F}}_q^2:x_1{x}_2\in {\square }_q^{*}\}.$$(2) , and (3)(3) $$S_3={\mathbb{F}}_q^2\setminus (S_1\cup S_2\cup \{\mathbf{0}\})$$(3) , respectively. Let ${\Gamma }_i=\text{Cay}({\mathbb{F}}_q^2,S_i)$, i = 1, 2, 3, be their corresponding Cayley graphs defined above. Then $\text{Aut} {\Gamma }_i$ contains F as a subgroup for each $i=1,2,3.$

Proof.

First, it is obvious that ${\lambda }_{(a,b)}$ and R are permutations of $V(\Gamma i),i=1,2,3$. By Pigeonhole’s Principle, it is enough to show that $M_a^{\pm }$ and A_i, i = 1, 2, are one-to-one.

Now: (i) $M_a^{+}(x_1,x_2)=M_a^{+}(y_1,y_2):\iff (a{x}_1,a{x}_2)=(a{y}_1,a{y}_2)\iff (x_1,x_2)=(y_1,y_2).$

(ii) $M_a^{-}(x_1,x_2)=M_a^{-}(y_1,y_2):\iff (a{x}_1,a^{-1}{x}_2)=(a{y}_1,a^{-1}{y}_2).$ This implies that ax₁ = ay₁ and $a^{-1}{x}_2=a^{-1}{y}_2.$ Thus $(x_1,x_2)=(y_1,y_2).$

(iii) For $A_1(x_1,x_2)=A_1(y_1,y_2)$, we have $(x_1^p,x_2)=(y_1^p,y_2)$ if and only if $(x_1,x_2)=(y_1,y_2).$ Similarly, $A_2(x_1,x_2)=A_2(y_1,y_2)$ if and only if $(x_1,x_2)=(y_1,y_2).$ Thus every element of F is a permutation of ${\mathbb{F}}_q^2.$

For adjacency, ${\lambda }_{(a,b)}$ are left translations. It is a classical result that they are automorphisms of Cayley graphs. Hence they are automorphisms of Γ_i, $i=1,2,3.$ Since $R,M_a^{\pm },A_i$, i = 1, 2, stabilize $\mathbf{0}$, it is enough to show that the image of $\mathbf{x}:=(x_1,x_2)$ by the above permutation is also an element of S_i, $i=1,2,3.$ Clearly, $(x,y)\in S_i$ if and only if $(y,x)\in S_i$, for each $i=1,2,3.$ For any $(x,y)\in S_i$, i = 1, 2; i.e., $xy\in {\square }_q$, we have that $$\begin{array}{c}{N}^{\varphi }(ax,ay)=a^{2}xy;\\ N^{\varphi }(ax,a^{-1}y)=xy;\\ N^{\varphi }(x^p,y)=x^{p}y=x^{p-1}·xy\in {\square }_q \text{since} p \text{is} \text{odd};\\ N^{\varphi }(x,y^p)=x{y}^p=xy·y^{p-1}\in {\square }_q \text{since} p \text{is} \text{odd}.\end{array}$$

Similar arguments hold as the latter are also valid for $(x,y)\in S_3$; i.e., $xy\notin {\square }_q.$ Hence R, $M_a^{\pm }$, and A_i, i = 1, 2, are automorphisms of Γ_i, $i=1,2,3.$ Therefore F is a subgroup of $\text{Aut} {\Gamma }_i.$ □

Let Λ be the subgroup of F generated by all translations ${\lambda }_{(a,b)}$ with $a,b\in {\mathbb{F}}_q.$ The following properties of F hold.

Lemma 2.

[7, Lemma 6] With notation as above we have the following:

1. Λ is normal in F.

2. $\left|F\right|={(q(q-1)r)}^2.$

3. The stabilizer $F_{\mathbf{0}}$ has orbits $S_0=\left\{\mathbf{0}\right\}$, S₁, S₂, and S₃; where S₁ and S₂ are given by equations (1)(1) $$S_1=\{(x_1,x_2)\in {\mathbb{F}}_q^2\setminus \{(0,0)\}:x_1{x}_2=0\}=({\mathbb{F}}_q^{*},0)\cup (0,{\mathbb{F}}_q^{*});$$(1) and (2)(2) $$S_2=\{(x_1,x_2)\in {\mathbb{F}}_q^2:x_1{x}_2\in {\square }_q^{*}\}.$$(2) respectively; and $S_3={\mathbb{F}}_q^2\setminus (S_0\cup S_1\cup S_2).$ In particular, F has rank 4.

4. F is primitive.

The orbits S_i, i = 1, 2, 3, given in (iii) of Lemma 2 are obviously the Cayley sets in the constituent graphs ${\Gamma }_i=\text{Cay}({\mathbb{F}}_q^2,S_i)$ as stated above. What follows next, is to study the automorphism groups of each Γ_i, i = 1, 2, 3, the main thrust of the paper. First, we look at the automorphism group of ${\Gamma }_1.$

3.1 The automorphism group of ${\Gamma }_1=\text{Cay}({\mathbb{F}}_q^2,S_1)$

In this section, we fully determine the automorphism group of ${\Gamma }_1=\text{Cay}({\mathbb{F}}_q^2,S_1)$ with $S_1=({\mathbb{F}}_q^{*},0)\cup (0,{\mathbb{F}}_q^{*})=\{(x_1,x_2)\in {\mathbb{F}}_q^2\setminus \{(0,0)\}:x_1{x}_2=0\}.$ Let $\mathbf{x}:=(x_1,x_2)$ and $\mathbf{y}:=(y_1,y_2)$ be vertices in ${\Gamma }_1.$ Then $\mathbf{x}$ and $\mathbf{y}$ are adjacent in ${\Gamma }_1$ if and only if $$N^{\varphi }(\mathit{x}-\mathit{y})=(x_1-y_1)(x_2-y_2)=0; \mathrm{i}.\mathrm{e}.,$$

x_i = y_i for exactly one i = 1,2. We shall say that $\sigma \in \text{Aut} {\Gamma }_1$ if and only if $$N^{\varphi }(\mathit{x}-\mathit{y})=0\iff N^{\varphi }({\mathit{x}}^{\sigma }-{\mathit{y}}^{\sigma })=0.$$

Since ${\Gamma }_1$ is vertex-transitive, it is sufficient to determine the stabilizer ${(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}$ of (0, 0) in $\text{Aut} {\Gamma }_1$ (by Orbit-Stabilizer Theorem).

In the subgroup ${(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}$, σ will permute only the non-zero vectors of ${\mathbb{F}}_q^2.$ Here, it can be shown that any permutation in ${\mathbb{F}}_q^{*}$ for exactly one component and any permutation of components in any element of ${\mathbb{F}}_q^2$ is an element of the subgroup ${(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}$ in the following result.

Lemma 3.

Let H be a permutation group of $V({\Gamma }_1)$ generated by $$R:(x_1,x_2)\mapsto (x_2,x_1);$$

${\pi }_{{\sigma }_1}:(x_1,x_2)\mapsto (x_1^{{\sigma }_1},x_2)$ and

${\pi }_{{\sigma }_2}:(x_1,x_2)\mapsto (x_1,x_2^{{\sigma }_2})$ where ${\sigma }_1,{\sigma }_2\in S_{{\mathbb{F}}_q}$ and $0^{{\sigma }_i}=0,i=1,2.$

Then H is a subgroup of the stabilizer ${(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}$ of (0, 0) in $\text{Aut} {\Gamma }_1.$

Proof.

Clearly, R, ${\pi }_{{\sigma }_i}$, i = 1, 2, stabilize (0,0). In order to show that H is a subgroup of ${(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}$, it is sufficient to show that R, ${\pi }_{{\sigma }_i}$, i = 1, 2, preserve the adjacency structure in ${\Gamma }_1.$

For any vertices $\mathbf{x}=(x_1,x_2)$ and $\mathbf{y}=(y_1,y_2)$ in ${\Gamma }_1,\{\mathbf{x},\mathbf{y}\}\in E({\Gamma }_1)$ if and only if $(x_1-y_1)(x_2-y_2)=0.$ It follows that $N^{\varphi }({\mathbf{x}}^R-{\mathbf{y}}^R)=(x_2-y_2)(x_1-y_1)=0.$ Thus $R\in {(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}.$ For ${\pi }_{{\sigma }_1}:(x_1,x_2)\mapsto (x_1^{{\sigma }_1},x_2)$, we have $$N^{\varphi }({\mathit{x}}^{{\pi }_{{\sigma }_1}}-{\mathit{y}}^{{\pi }_{{\sigma }_1}})=(x_1^{{\sigma }_1}-y_1^{{\sigma }_1})(x_2-y_2).$$

Since σ₁ is a permutation of ${\mathbb{F}}_q$, it follows that $x_1^{{\sigma }_1}=y_1^{{\sigma }_1}\iff x_1=y_1.$ However, if x₁ = y₁, then $\mathbf{x}$ is adjacent to $\mathbf{y}.$ Thus ${\mathbf{x}}^{{\pi }_{{\sigma }_1}}$ is adjacent to ${\mathbf{y}}^{{\pi }_{{\sigma }_1}}.$ With a similar argument applied to ${\pi }_{{\sigma }_1}$, it can also be shown that ${\pi }_{{\sigma }_2}$ preserves the adjacency structure of ${\Gamma }_1.$ Therefore $H=〈R,{\pi }_{{\sigma }_i},i=1,2〉$ is a subgroup of the stabilizer ${(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}$ of (0, 0) in $\text{Aut} {\Gamma }_1.$ □

As we have just shown that H is a subgroup of ${(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}$, we also show the maximality of H in the symmetric group $S_{S_1}.$ (See further details of maximal subgroups of a symmetric group in [1, 12]).

Lemma 4.

Let H be defined as in Lemma 3. H is a maximal subgroup of the symmetric group $S_{S_1}$, where S₁ is the Cayley set of ${\Gamma }_1.$

Proof.

Consider the action of H on $S_1=({\mathbb{F}}_q^{*},0)\cup (0,{\mathbb{F}}_q^{*}).$ Let $\Delta =({\mathbb{F}}_q^{*},0).$ Then we have ${\Delta }^R=(0,{\mathbb{F}}_q^{*})$, and ${\Delta }^{{\pi }_{{\sigma }_1}}={\Delta }^{{\pi }_{{\sigma }_2}}=\Delta .$ So $({\mathbb{F}}_q^{*},0)$ and $(0,{\mathbb{F}}_q^{*})$ are blocks for H.

Let ${\Delta }_1=({\mathbb{F}}_q^{*},0)$ and ${\Delta }_2=(0,{\mathbb{F}}_q^{*}).$ Then it is shown by [12, Proposition 2.1] that the subgroup of $S_{S_1}$ isomorphic to $S_{{\Delta }_i}{\wr }_{[2]}{S}_{[2]}$ is maximal in $S_{S_1}$ (we use the notation $S_{[2]}$ for a symmetric group instead of S₂ for a Cayley set). This is also isomorphic to the wreath product $S_{{\mathbb{F}}_q^{*}}\wr S_{[2]}$.

Hence it is sufficient to check whether H is isomorphic with the wreath product of $S_{{\mathbb{F}}_q^{*}}$ by $S_{[2]}.$ Here we check the normality of R and ${\pi }_{{\sigma }_i}$, i = 1, 2, in H. Let us determine the conjugates of R with ${\pi }_{{\sigma }_i}$, i = 1, 2, and the conjugates of ${\pi }_{{\sigma }_i}$ by ${\pi }_{{\sigma }_i}$ and R, $i,j=1,2$ and $i\ne j.$ Clearly, we have $R=R^{-1}$, ${\pi }_{{\sigma }_1}^{-1}:(x_1,x_2)\mapsto (x_1^{{\sigma }_1^{-1}},x_2)$, and ${\pi }_{{\sigma }_2}^{-1}:(x_1,x_2)\mapsto (x_1,x_2^{{\sigma }_2^{-1}}).$

It is easily shown that ${(x_1,x_2)}^{R^{-1}{\pi }_{{\sigma }_1}R}=(x_1,x_2^{{\sigma }_1}) \text{and}$ ${(x_1,x_2)}^{{\pi }_{{\sigma }_1}^{-1}{\pi }_{{\sigma }_1}{\pi }_{{\sigma }_2}}=(x_1^{{\sigma }_1},x_2).$ This implies that $R^{-1}{\pi }_{{\sigma }_1}R={\pi }_{{\sigma }_2} \text{and} {\pi }_{{\sigma }_2}^{-1}{\pi }_{{\sigma }_1}{\pi }_{{\sigma }_2}={\pi }_{{\sigma }_1}.$ Similarly, we have $R^{-1}{\pi }_{{\sigma }_2}R={\pi }_{{\sigma }_1} \text{and} {\pi }_{{\sigma }_1}^{-1}{\pi }_{{\sigma }_2}{\pi }_{{\sigma }_1}={\pi }_{{\sigma }_2}.$ It follows that ${\pi }_{{\sigma }_1}$ and ${\pi }_{{\sigma }_2}$ commute, and R interchanges ${\pi }_{{\sigma }_1}$ with ${\pi }_{{\sigma }_2}.$ Thus $〈{\pi }_{{\sigma }_1},{\pi }_{{\sigma }_2}〉=〈{\pi }_{{\sigma }_1}〉\times 〈{\pi }_{{\sigma }_2}〉$ is normal in H, where $〈{\pi }_{{\sigma }_i}〉$ is isomorphic with $S_{{\mathbb{F}}_q^{*}}$, i = 1, 2, and R is isomorphic with $S_{[2]}.$ Hence $H\cong (S_{{\mathbb{F}}_q^{*}}\times S_{{\mathbb{F}}_q^{*}})⋊S_{[2]}=S_{{\mathbb{F}}_q^{*}}\wr S_{[2]}.$ Therefore H is maximal in $S_{S_1}.$ □

From the above result, it is convenient to identify the subgroup H of ${(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}$ with the wreath product $S_{{\mathbb{F}}_q^{*}}\wr S_{[2]}.$ Now we have to prove the converse of Lemma 3 to obtain the following.

Corollary 1.

$H={(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}.$

Proof.

By maximality of H, this follows immediately. □

As the conclusion on this matter, we have the following result.

Theorem 4.

Let ${\Gamma }_1=\text{Cay}({\mathbb{F}}_q^2,S_1)$ with $S_1=({\mathbb{F}}_q^{*},0)\cup (0,{\mathbb{F}}_q^{*}).$ Let H and $\Lambda =〈{\lambda }_{(a,b)}〉$ be the subgroups of $\text{Aut} {\Gamma }_1$ defined above. Then

1. $\text{Aut} {\Gamma }_1=\Lambda H$;

2. $|\text{Aut} {\Gamma }_1|=2{(q!)}^2.$

Proof.

(i) Clearly, the regular subgroup $\Lambda =〈{\lambda }_{(a,b)}〉$ of $\text{Aut} {\Gamma }_1$ is the orbit of the vector (0, 0) in $\text{Aut} {\Gamma }_1.$ By Corollary 1, $H=〈R,{\pi }_{{\sigma }_i},i=1,2〉$ is the stabilizer of $(0,0)$ in $\text{Aut} {\Gamma }_1$ Thus (i) follows by Orbit-Stabilizer Theorem.

(ii) Now we determine the order of $\text{Aut} {\Gamma }_1.$ First we have $\left|\Lambda \right|=|〈{\lambda }_{(a,b)}〉|=q^2$; and $\left|H\right|=\left|S_{{\mathbb{F}}_q^{*}}\wr S_{[2]}\right|=2{((q-1)!)}^2.$ Thus by Orbit-Stabilizer Theorem, we obtain $$\begin{array}{c}|\text{Aut} {\Gamma }_1|=\left|{\mathbf{0}}^{\text{Aut} {\Gamma }_1}\right|\left|{(\text{Aut} {\Gamma }_1)}_{\mathbf{0}}\right|\\ =\left|\Lambda \right|·\left|H\right|\\ =q^2·2{((q-1)!)}^2\\ =2{(q!)}^2.\end{array}$$

□

3.2 The automorphism groups of ${\Gamma }_2=\text{Cay}({\mathbb{F}}_q^2,S_2)$ and ${\Gamma }_3=\text{Cay}({\mathbb{F}}_q^2,S_3)$ with $S_3={\mathbb{F}}_q^2\setminus (S\cup \{\mathbf{0}\}),S=S_1\cup S_2$

In this section, we determine the automorphism group of ${\Gamma }_2=\text{Cay}({\mathbb{F}}_q^2,S_2)$ with $S_2=\{(x_1,x_2)\in {\mathbb{F}}_q^2:x_1{x}_2\in {\square }_q\setminus \{0\left\}\right\}.$ Recall that if given $\mathbf{s}\in S_2,\mathbf{x}$ and $\mathbf{y}$ are adjacent vertices in ${\Gamma }_2$ if and only if $\mathbf{x}-\mathbf{y}=\mathbf{s}.$

Put $\mathbf{x}:=(x_1,x_2)$ and $\mathbf{y}:=(y_1,y_2).$ Then we have $\mathbf{s}=(x_1-y_1,x_2-y_2).$ That is, $\mathbf{s}\in S_2$ if and only if $(x_1-y_1)(x_2-y_2)\in {\square }_q\setminus \left\{0\right\}.$ This implies that the corresponding components should not equal as in the previous case of ${\Gamma }_1$; i.e., $x_1\ne y_1$ and $x_2\ne y_2.$

By Lemma 1, $\text{Aut} {\Gamma }_2$ contains the group F generated by the permutations ${\lambda }_{a,b}$, R, $M_a^{\pm }$, and A_i, i = 1, 2, and hence primitive by Lemma 2(iv). According to the results from Theorem 2 and Lemma 1, we find that the results for this case are the same as in Lemmas 1 and 2, so that $\text{Aut} {\Gamma }_2$ and $\text{Aut} \Gamma ,\Gamma =\text{Cay}({\mathbb{F}}_q^2,S)$, may be isomorphic.

To see the isomorphism between $\text{Aut} {\Gamma }_2$ and $\text{Aut} \Gamma$, we have to look at the isomorphism of graphs ${\Gamma }_2=\text{Cay}({\mathbb{F}}_q^2,S_2)$ and ${\Gamma }_3=\text{Cay}({\mathbb{F}}_q^2,S_3)$, with $S_3={\mathbb{F}}_q^2\setminus (S\cup \{\mathbf{0}\}),S=S_1\cup S_2.$

Lemma 5.

Consider the graphs ${\Gamma }_2=\text{Cay}({\mathbb{F}}_q^2,S_2)$ and ${\Gamma }_3=\text{Cay}({\mathbb{F}}_q^2,S_3)$ with $S_3={\mathbb{F}}_q^2\setminus (S_1\cup S_2\cup \{\mathbf{0}\}).$ The linear mapping ${\tau }_{\alpha }:V({\Gamma }_2)\to V({\Gamma }_3)$ defined by $${\tau }_{\alpha }:(x_1,x_2)\mapsto (\alpha x_1,x_2) \text{with} \alpha \notin {\square }_q$$is an automorphism of ${\mathbb{F}}_q^2.$

Proof.

It can be easily verified that ${\tau }_{\alpha }$ is ${\mathbb{F}}_q$-linear. Now, suppose that we have ${\mathbf{x}}^{{\tau }_{\alpha }}={\mathbf{y}}^{{\tau }_{\alpha }}.$ Then ${(x_1,x_2)}^{{\tau }_{\alpha }}={(y_1,y_2)}^{{\tau }_{\alpha }}:\iff (\alpha x_1,x_2)=(\alpha y_1,y_2).$ This is equivalent to $\alpha x_1=\alpha y_1$ and $x_2=y_2.$ Thus x₁ = y₁ and $x_2=y_2.$ By Pigeonhole’s Principle it follows that ${\tau }_{\alpha }$ is a bijection and hence an automorphism of ${\mathbb{F}}_q^2.$ □

Corollary 2.

Let ${\Gamma }_2$ and ${\Gamma }_3$ be graphs defined above. Then

1. ${\Gamma }_2\cong {\Gamma }_3$;

2. $\text{Aut} \Gamma =\text{Aut} {\Gamma }_3\cong \text{Aut} {\Gamma }_2.$

Proof.

(i) Consider the Cayley sets S₂ and S₃ corresponding to the graphs ${\Gamma }_2$ and ${\Gamma }_3$, respectively.

Let $\mathbf{x}:=(x_1,x_2)$ be an element of $S_2.$ Then $N^{\varphi }(\mathbf{x})=x_1{x}_2\in {\square }_q\setminus \left\{0\right\}.$ With the linear mapping ${\tau }_{\alpha }:V({\Gamma }_2)\to V({\Gamma }_3)$ defined in Lemma 5 for any $\alpha \notin {\square }_q$, it follows that ${\mathbf{x}}^{{\tau }_{\alpha }}=(\alpha x_1,x_2) \text{and} N^{\varphi }({\mathbf{x}}^{{\tau }_{\alpha }})=\alpha x_1{x}_2\notin {\square }_q.$ Thus ${\mathbf{x}}^{{\tau }_{\alpha }}\in {\mathbb{F}}_q^2\setminus (S_1\cup S_2\cup \{\mathbf{0}\})=S_3$ and hence $S_2^{{\tau }_{\alpha }}\subseteq S_3.$ Since ${\tau }_{\alpha }$ is an automorphism of ${\mathbb{F}}_q^2$ by Lemma 5, it follows that $S_2^{{\tau }_{\alpha }}=S_3.$ Therefore, (i) follows immediately by Proposition 1.

(ii) This follows immediately from (i) since ${\Gamma }_3$ is the complement of $\Gamma .$ □

With the results above, we conclude that the automorphism group of ${\Gamma }_i=\text{Cay}({\mathbb{F}}_q^2,S_i)$, i = 2, 3, is isomorphic to the automorphism group of $\Gamma =\text{Cay}({\mathbb{F}}_q^2,S),S=S_1\cup ,S_2.$ Hence, it is sufficient to determine $\text{Aut} \Gamma .$

For the graph $\Gamma =\text{Cay}({\mathbb{F}}_q^2,S)$ with the proof of Lemma 1, it can be deduced that $\text{Aut} \Gamma$ contains the group F generated by ${\lambda }_{(a,b)}$, R, $M_a^{\pm }$, and A_i, i = 1, 2, defined in the beginning of this section.

Recall that $S={\mathbb{S}}^{\varphi }$ so that $\text{Aut} \Gamma =\text{Aut}(\text{Cay}({\mathbb{F}}_q^2,{\mathbb{S}}^{\varphi }))={\varphi }^{-1}\text{Aut}({\mathbb{F}}_q^2)\varphi .$ Let $G:=\varphi F{\varphi }^{-1}\le \text{Aut}({\mathbb{F}}_q^2).$ Then $\left|G\right|={(q(q-1)r)}^2$ by Lemma 2. Hence, it follows that G is isomorphic to the group $〈\text{AffAut}({\mathbb{F}}_q^2),\psi 〉$ described in [6].

Since $\text{Cay}({\mathbb{F}}_q^2,\mathbb{S})$ is isomorphic to Γ, Theorem 2 is equivalent to the following statement with further details for a proof given in [7].

Theorem 5.

[7, Theorem 5] With notations as above, if $q\notin \{5,9\}$, then $|\text{Aut} \Gamma |={(q(q-1)r)}^2.$

From the former results with Theorem 4, we determine the orders of $\text{Aut} {\Gamma }_2$ and $\text{Aut} {\Gamma }_3$ in the following.

Corollary 3.

Let ${\Gamma }_2=\text{Cay}({\mathbb{F}}_q^2,S_2)$ and ${\Gamma }_3=\text{Cay}({\mathbb{F}}_q^2,S_3),q\notin \{5,9\}$, with $S_2=\{(x_1,x_2)\in {\mathbb{F}}_q^2:x_1{x}_2{\square }_q^{*}\}$ and $S_3={\mathbb{F}}_q^2\setminus (S\cup \{\mathbf{0}\}),S=S_1\cup S_2.$ Then $$|\text{Aut} {\Gamma }_2|=|\text{Aut} {\Gamma }_3|={(q(q-1)r)}^2.$$

Proof.

This follows immediately from Theorem 4 and Corollary 2(ii) □