![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
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 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
and
which inherit the properties of
It will be shown that
is isomorphic to
and that
is isomorphic to
1 Introduction
In this paper, all considered graphs are assumed to be finite, simple and connected. A graph is a set V of vertices together with a relation E, which is irreflexive and symmetric. If in
, 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
,
and {x, y} denote the vertex set, the edge set, and an edge with endpoints x and y in
, respectively. For an edge {x, y}, x and y are said to be adjacent in
For digraphs, arcs are represented by pairs of the form
By the complement of Γ is meant a graph
with
such that
if and only if
Let Γ and Λ be graphs. By a graph isomorphism between Γ and Λ is meant a bijection such that
if and only if
and if Γ is isomorphic to Λ, it is denoted by
By a self-complementary graph is meant a graph Γ isomorphic to its complement. If σ is a permutation of
that preserves adjacency relations, then it is called an automorphism of
By the automorphism group of Γ, denoted by
, is meant the set of all automorphisms of
Γ is vertex-transitive if
is transitive on
i.e.,
is a single orbit under the action of
Let G be a group and an identity element of G. Let S be a subset of G such that
and
By the Cayley graph
is meant a graph defined by
and
The set S is called a Cayley set on G. It is a classical result that for
, the subset
is a Cayley set on G for the complementary graph
The mapping defined by
, is clearly an automorphism of
It is immediate therefore that,
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.
[Citation3, Lemma 3.7.3] Let be an automorphism of the group G and let S be a Cayley set of G. Then
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 for each
and
Denote by
the elementwise stabilizer of Δ in G; while
denotes the setwise stabilizer of Δ in G. If
, then
denotes
; in particular,
denotes
If in addition, G acts transitively on Ω, a subset
is called a block for G if for every
or
The sets
, form a partition of Ω which is called a system of blocks for G containing
If G is transitive on Ω, then it is clear that Ω and the singletons
(
) 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 coordinatewise, and the respective orbits are called the orbitals of G. Since G is transitive on Ω, the set
is an orbital, explicitly called the diagonal orbital of G. Given an orbital Δ of G, the orbital digraph
is defined to have vertex set Ω and arc set
The number of orbits of the stabilizer
is equal to the number of the orbitals of G for any
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 over the finite field
p prime and
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 for
to be used in Section 3.2. We shall look at the automorphism groups of the constituent graphs
, i = 1, 2, 3, of
,
, with Si, i = 1, 2, the two base subsets of
to be defined in Section 3, and
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
with the wreath product of the symmetric group
by
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
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 as a set of points with pairwise integral distances in the Euclidean metric; see [Citation5, Citation6, Citation8–10]. Here we consider such a concept to inner product spaces
over a finite field
, p prime.
It turns out that it is useful to model integral point sets as cliques of certain graphs. For a given prime power and a given dimension, a graph of integral distance is a graph
with vertex set
, where two vertices
and
form an edge in it, if they are at integral distance. In [Citation4], integral distance graphs
were shown to be Cayley and strongly regular for
as well as their constituent graphs for m = 2 and
that we shall define in Section 3. The automorphism groups of
have been described by Kovács et al. [Citation7] and by Kurz et al. [Citation6, Citation9, Citation10]. For
, the graph
can be shown to be isomorphic to the Paley graph
of square order; see [Citation6, Citation7, Citation10]. Our point of interest for symmetries will only focus on the two-dimensional case for
Here, we shall only deal with automorphism groups of the constituent graphs of
For the finite field of order
, p prime,
denotes the set of all perfect squares in
including the zero element. The norm
of a point
is defined by
, and two points
are said to be at integral distance if
That is, the norm
can be interpreted on the squared Euclidean distance between
and
For a line
with
is called the direction of
If
, then
is an integral direction. If
, then
is a vanishing direction.
In the finite field , it is shown in [Citation2] that
for
However, for
so that
is irreducible. Here,
can be considered as
where i is a root of the polynomial
In addition,
can be identified as
which is a field, see [Citation6, Citation7, Citation9].
The following parametric representation of pairs of is very important. It will be a very useful result in some of the counting arguments in the rest of the paper.
Theorem 1.
[Citation6, Citation10] Let and denote
for
Then
Moreover,
For , the points
can be represented in another basis of
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
in which the norm of
in that new basis is
with vanishing directions
and
See further details in [Citation6].
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 is meant a permutation σ of
which preserves the integral distances; i.e., for all
,
If additionally the permutation σ is an element of the affine semi-linear group , then σ is called an affine integral automorphism.
The group of all integral automorphisms and those of all affine integral automorphisms are denoted by and
, respectively.
is exactly the automorphism group of the graph of integral distances
It is clear that
is a subgroup of
[Citation6]. Now the following are the characterizations of the affine integral automorphisms of
Theorem 2.
[Citation6, Citation9] Let Then
is generated by
the translations
for all
;
the reflexion
;
the spiral collineations
for
with
; and,
The Frobenius automorphisms
, with p the characteristic of
In [Citation9], it has been shown that no other permutation of than those mentioned above is an affine integral automorphism of
Now in Theorem 2, with counting arguments, the orders of
and
are 2, r and
respectively. With the same argument, since
is a subgroup of
a multiplicative cyclic group, we have that
Hence, with the help of Theorem 1 for the order of
it follows that
The details of automorphism groups of for
were given in [Citation9]. In either that case or
q prime, it has been shown in [6, Theorem 9] that
In the remaining case; namely,
and
the map
was shown to be an integral automorphism of
but not an affine automorphism, so that
and
are not isomorphic, see [6, Theorem 13]. In the latter case with
it was conjectured in [Citation6] that
Hence this lead to the following.
Theorem 3.
[7, Theorem 1] Let , where p is a prime and
Then
3 Automorphism groups of the constituent graphs of ![](//:0)
![](//:0)
![](//:0)
By [4, Proposition 3.10], it is shown that is a Cayley graph
where
is the connecting set of the integral distance graph.
For , there exists
such that
The linear mapping
defined in [Citation7] maps the graph
to
where
; i.e.,
is a switch to hyperbolic coordinates, see [Citation7].
We set and
Here we consider the two base subsets S1 and S2 of
defined by
(1)
(1) and
(2)
(2)
Clearly, It is easy to show that Si, i = 1, 2, are Cayley sets in the addition group
so that we have the Cayley graphs
by [4, Lemma 3.2, Corollary 3.3]. It is also shown in [Citation4, Citation11] that the subsets Si, i = 1, 2, of
form a basis of Boolean algebra
of Cayley sets so that
is a Cayley graph by [4, Corollary 3.3]. In addition, we shall consider another subset
(3)
(3) so that we have another Cayley graph
by [4, Corollary 3.3]. The three graphs
, i = 1, 2, 3, are called in this paper the constituent graphs of the integral distance graphs over
As a starting point, the following permutations of have already been defined in [Citation7].
Let F be the group generated by the permutations of defined above. We shall show that F is a subgroup of
, where
, i = 1, 2, 3, with S1 and S2 the base subsets of
defined above; and S3 the complement of
in
In addition, it is easy to show that F is also generated by the conjugates of the elements of from Theorem 2 by the
-linear mapping
,
, together with the mapping ψ defined in Section 2.
Moreover, it is shown that F in its action on , i = 1, 2, 3, is primitive, see Lemma 2. That is,
, i = 1, 2, 3, is therefore primitive.
We first show that F is a subgroup of
Lemma 1.
Let S1, S2 and S3 be defined as in EquationEquations (1)(1)
(1) , Equation(2)
(2)
(2) , and Equation(3)
(3)
(3) , respectively. Let
, i = 1, 2, 3, be their corresponding Cayley graphs defined above. Then
contains F as a subgroup for each
Proof.
First, it is obvious that and R are permutations of
. By Pigeonhole’s Principle, it is enough to show that
and Ai, i = 1, 2, are one-to-one.
Now: (i)
(ii) This implies that ax1 = ay1 and
Thus
(iii) For , we have
if and only if
Similarly,
if and only if
Thus every element of F is a permutation of
For adjacency, are left translations. It is a classical result that they are automorphisms of Cayley graphs. Hence they are automorphisms of Γi,
Since
, i = 1, 2, stabilize
, it is enough to show that the image of
by the above permutation is also an element of Si,
Clearly,
if and only if
, for each
For any
, i = 1, 2; i.e.,
, we have that
Similar arguments hold as the latter are also valid for ; i.e.,
Hence R,
, and Ai, i = 1, 2, are automorphisms of Γi,
Therefore F is a subgroup of
□
Let Λ be the subgroup of F generated by all translations with
The following properties of F hold.
Lemma 2.
[7, Lemma 6] With notation as above we have the following:
Λ is normal in F.
The stabilizer
has orbits
, S1, S2, and S3; where S1 and S2 are given by Equationequations (1)
(1)
(1) and Equation(2)
(2)
(2) respectively; and
In particular, F has rank 4.
F is primitive.
The orbits Si, i = 1, 2, 3, given in (iii) of Lemma 2 are obviously the Cayley sets in the constituent graphs 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
3.1 The automorphism group of ![](//:0)
![](//:0)
In this section, we fully determine the automorphism group of with
Let
and
be vertices in
Then
and
are adjacent in
if and only if
xi = yi for exactly one i = 1,2. We shall say that if and only if
Since is vertex-transitive, it is sufficient to determine the stabilizer
of (0, 0) in
(by Orbit-Stabilizer Theorem).
In the subgroup , σ will permute only the non-zero vectors of
Here, it can be shown that any permutation in
for exactly one component and any permutation of components in any element of
is an element of the subgroup
in the following result.
Lemma 3.
Let H be a permutation group of generated by
and
where
and
Then H is a subgroup of the stabilizer of (0, 0) in
Proof.
Clearly, R, , i = 1, 2, stabilize (0,0). In order to show that H is a subgroup of
, it is sufficient to show that R,
, i = 1, 2, preserve the adjacency structure in
For any vertices and
in
if and only if
It follows that
Thus
For
, we have
Since σ1 is a permutation of , it follows that
However, if x1 = y1, then
is adjacent to
Thus
is adjacent to
With a similar argument applied to
, it can also be shown that
preserves the adjacency structure of
Therefore
is a subgroup of the stabilizer
of (0, 0) in
□
As we have just shown that H is a subgroup of , we also show the maximality of H in the symmetric group
(See further details of maximal subgroups of a symmetric group in [Citation1, Citation12]).
Lemma 4.
Let H be defined as in Lemma 3. H is a maximal subgroup of the symmetric group , where S1 is the Cayley set of
Proof.
Consider the action of H on Let
Then we have
, and
So
and
are blocks for H.
Let and
Then it is shown by [12, Proposition 2.1] that the subgroup of
isomorphic to
is maximal in
(we use the notation
for a symmetric group instead of S2 for a Cayley set). This is also isomorphic to the wreath product
.
Hence it is sufficient to check whether H is isomorphic with the wreath product of by
Here we check the normality of R and
, i = 1, 2, in H. Let us determine the conjugates of R with
, i = 1, 2, and the conjugates of
by
and R,
and
Clearly, we have
,
, and
It is easily shown that
This implies that
Similarly, we have
It follows that
and
commute, and R interchanges
with
Thus
is normal in H, where
is isomorphic with
, i = 1, 2, and R is isomorphic with
Hence
Therefore H is maximal in
□
From the above result, it is convenient to identify the subgroup H of with the wreath product
Now we have to prove the converse of Lemma 3 to obtain the following.
Corollary 1.
Proof.
By maximality of H, this follows immediately. □
As the conclusion on this matter, we have the following result.
Theorem 4.
Let with
Let H and
be the subgroups of
defined above. Then
;
Proof.
(i) Clearly, the regular subgroup of
is the orbit of the vector (0, 0) in
By Corollary 1,
is the stabilizer of
in
Thus (i) follows by Orbit-Stabilizer Theorem.
(ii) Now we determine the order of First we have
; and
Thus by Orbit-Stabilizer Theorem, we obtain
□
3.2 The automorphism groups of ![](//:0)
and ![](//:0)
with ![](//:0)
![](//:0)
In this section, we determine the automorphism group of with
Recall that if given
and
are adjacent vertices in
if and only if
Put and
Then we have
That is,
if and only if
This implies that the corresponding components should not equal as in the previous case of
; i.e.,
and
By Lemma 1, contains the group F generated by the permutations
, R,
, and Ai, 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
and
, may be isomorphic.
To see the isomorphism between and
, we have to look at the isomorphism of graphs
and
, with
Lemma 5.
Consider the graphs and
with
The linear mapping
defined by
is an automorphism of
Proof.
It can be easily verified that is
-linear. Now, suppose that we have
Then
This is equivalent to
and
Thus x1 = y1 and
By Pigeonhole’s Principle it follows that
is a bijection and hence an automorphism of
□
Corollary 2.
Let and
be graphs defined above. Then
;
Proof.
(i) Consider the Cayley sets S2 and S3 corresponding to the graphs and
, respectively.
Let be an element of
Then
With the linear mapping
defined in Lemma 5 for any
, it follows that
Thus
and hence
Since
is an automorphism of
by Lemma 5, it follows that
Therefore, (i) follows immediately by Proposition 1.
(ii) This follows immediately from (i) since is the complement of
□
With the results above, we conclude that the automorphism group of , i = 2, 3, is isomorphic to the automorphism group of
Hence, it is sufficient to determine
For the graph with the proof of Lemma 1, it can be deduced that
contains the group F generated by
, R,
, and Ai, i = 1, 2, defined in the beginning of this section.
Recall that so that
Let
Then
by Lemma 2. Hence, it follows that G is isomorphic to the group
described in [Citation6].
Since is isomorphic to Γ, Theorem 2 is equivalent to the following statement with further details for a proof given in [Citation7].
Theorem 5.
[7, Theorem 5] With notations as above, if , then
From the former results with Theorem 4, we determine the orders of and
in the following.
Corollary 3.
Let and
, with
and
Then
Proof.
This follows immediately from Theorem 4 and Corollary 2(ii) □
References
- Ball, R. W. (1966). Maximal subgroups of symmetric groups. Trans. Amer. Math. Soc. 121(2): 393–407.
- Elsawy, A. N. (2009). Paley graphs and their generalisation Master’s Thesis. Heinrich Heine University, Dússeldorf, Germany.
- Godsil, C, Royle, G. (2001). Algebraic Graph Theory. New York: Springer-Verlag.
- Habineza, O. (2021). Graphs of Integral Distances and Their Properties PhD Thesis. University of the Western Cape, Bellville, South Africa.
- Iosevich, A, Rudnev, M. (2003). A combinatorial approach to orthogonal exponentials. Int. Math. Res. Not 49: 1–12.
- Kiermaier, M, Kurz, S. (2009). Maximal integral point sets in affine planes over finite fields. Discrete Math 309(13): 4564–4575.
- Kovács, I, Ruff, J. (2014). Integral automorphisms of affine planes over finite fields. Finite Fields Their Appl 27: 104–114.
- Kovács, I., Kutnar, K., Ruff, J, Szőnyi, T. (2017). Integral automorphisms of affine spaces over finite fields. Des Codes Cryptogr. 84(1-2): 181–188.
- Kurz, S. (2009). Integral point sets over finite fields. Australas J. Combin 43: 3–29.
- Kurz, S, Meyer, H. (2009). Integral point sets in higher dimensional affine spaces over finite fields. J. Comb. Theory, Ser. A 116(6): 1120–1139.
- Mwambene, E. (2001). Representing graphs on groupoids: symmetry and form PhD Thesis. University of Vienna, Vienna, Austria.
- Newton, B, Benesh, B. (2006). A classification of certain maximal subgroups of symmetric groups. J. Algebra 304(2): 1108–1113.