Normal edge-transitive Cayley graphs on a class of non-abelian groups

Abstract

Let Γ=Cay(G, S) be the Cayley graph of a group G with respect to its subset S. The graph Γ is said to be normal edge-transitive if the normalizer of G in the automorphism group Aut(Γ) of Γ acts transitively on the edge set of Γ. In this paper, we study the structure of normal edge-transitive Cayley graphs on a class of non-abelian groups with order 2p² (p refers to an odd prime). The structure and automorphism groups of the non-abelian groups are first presented, and then the tetravalent normal edge-transitive Cayley graphs on such groups are investigated. Finally, the normal edge-transitive Cayley graphs on group G are characterized and classified.

Keywords

Cayley graph / symmetric graph / normal edge-transitivity

1 Introduction

As one of the most significant concepts, the group has greatly promoted the development and application of algebra since it was first proposed by Évariste Galois in the early 19th century when he studied the roots of equations. Moreover, as a relatively old branch of mathematics, graph theory has been applied in various fields of modern science since the Swiss mathematician Leonhard Euler presented a solution to Königsberg bridge problem in 1735. Since then, the attention and research on graph theory have gradually increased, and many problems such as Sir William Rowan Hamilton’s famous “Icosian Game”, the four-color problem, and the Knight’s tour problem are closely related to it. Groups and graphs are closely related to each other. At the beginning of the 20th century, researchers started to use graphs to study groups, and groups were also applied in graph studies. In 1938, Frucht obtained a groundbreaking result that for any given abstract group, there is a graph taking the group as an automorphism group, which preluded the research combining the graph and group.

Algebraic graph theory is a very important branch of graph theory where Cayley graph draws much attention. At present, one of the hot issues in Cayley graphs research comes to its normality, especially the research of normal Cayley graphs and normal edge-transitive Cayley graphs. In this paper, we mainly study a class of normal edge-transitive Cayley graphs.

The concept of normal Cayley graph was first given by Chinese scholar Xu [14] in the 1990s, while the concept of normal edge-transitive Cayley graphs was first proposed by Praeger [11] in 1999. Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be the Cayley graph of a group G with respect to its subset S. The graph Γ is said to be normal edge-transitive if the normalizer of G in the automorphism group Aut(Γ) of Γ acts transitively on the edge set of Γ. We can see that if \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a normal Cayley graph and edge-transitive, Γ must be a normal edge-transitive Cayley graph. Conversely, if Γ is a normal edge-transitive Cayley graph, Γ must be edge-transitive, but Γ may not always be a normal Cayley graph.

In recent years, scholars at home and abroad have paid attention to normal Cayley graphs and normal edge-transitive Cayley graphs and have achieved much. In 2004, Fang et al. [7] studied tetravalent edge-transitive Cayley graphs on some non-abelian simple groups. In 2006, Li et al. [10] studied tetravalent edge-transitive Cayley graphs of odd order. In 2009, Alaeiyan [1] showed some normal edge-transitive Cayley graphs on abelian groups. In 2011, Talebi [13] studied normal edge-transitive Cayley graphs on dihedral groups. In 2013, Darafsheh and Assari [5] characterized normal edge-transitive Cayley graphs on non-abelian groups of order 4p with unrestricted degrees. In 2015, Corr and Praeger [3] characterized and classified normal edge-transitive Cayley graphs on Frobenius groups of order pq. In 2017, Sharifi and Darafsheh [12] studied tetravalent normal edge-transitive Cayley graphs on modules. In 2021, Zhou et al. [4] characterized and classified tetravalent non-normal Cayley graphs on non-abelian groups of order 2p².

Based on the above research background, in this paper, we study the structure of normal edge-transitive Cayley graphs on a class of non-abelian groups. The structure and automorphism groups of the non-abelian groups are first presented, and then the tetravalent normal edge-transitive Cayley graphs on such groups are investigated. Finally, the normal edge-transitive Cayley graphs on such groups are characterized and classified.

Let group G be a non-abelian group with order 2p² under type G₃(p) (see Section 3 for details) and p refers to an odd prime. The main results of this paper are as follows.

Theorem 1.1　 Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be a connected tetravalent Cayley graph on group G with respect to its subset S. Γ is a normal edge-transitive Cayley graph if and only if . Denote \mathrm{A}\mathrm{u}\mathrm{t}(G,S)=\{\alpha \in \mathrm{A}\mathrm{u}\mathrm{t}(G\left)\right|S^{\alpha }=S\}, and then \mathrm{A}\mathrm{u}\mathrm{t}(G,S)\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2.

Theorem 1.2　 Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be the Cayley graph of group G with respect to its subset S. Γ is a connected normal edge-transitive Cayley graph if and only if the degree of Γ is even, , and S=S^{-1}. At this time, \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S, so Γ is a normal arc-transitive graph.

Theorem 1.3　 Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be a connected normal edge-transitive Cayley graph, and the degree of Γ is 2d. Then d=p, or d|\left(p-1\right), or \mathrm{d}|p\left(p-1\right),or d\mid \frac{(p-1{)}^2}{2}. For d meeting the requirements above, there is only one normal edge-transitive Cayley graph with degree 2d under isomorphism. At this time, \mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{C}\mathrm{a}\mathrm{y}\right(G,S\left)\right)\cong {\mathbb{Z}}_d\times {\mathbb{Z}}_2.

In Section 2, we briefly summarize some basic concepts and basic properties of permutation groups, Cayley graphs and normal edge-transitive Cayley graphs. In Section 3, we show the detailed proofs of the main theorems.

2 Preliminaries

2.1 Basic concepts of groups and graphs

Some basic concepts and results of groups and graphs used in this paper are shown in this section, and the notations and definitions used in this paper are standard (see also [2, 6, 15]).

Definition 2.1　Let H and K be two groups, and there is a homomorphism\tau :H\to \mathrm{A}\mathrm{u}\mathrm{t}\left(K\right). For each x∈H, the mapping u\mapsto u^x is an automorphism of K. Let

G=\left\{\right(u,x\left)\right|u\in K,x\in H\},

and define the multiplication on the group G as

(u,x)(v,y):=(u{v}^{x^{-1}},xy),\mathrm{\forall }(u,x),(v,y)\in G.

We can see that G forms a group based on the the above multiplication, called the semidirect product of K and H, and denoted by G=K⋊HorG=K:H.

Definition 2.2　The elements in V are called the vertices of Γ, and the elements in E are the edges of Γ. If the relation E is symmetric, that is, for any two vertices u and w, they are connected edges if and only if w and u are also edge-connected, then Γ will be called an undirected graph, or a graph. An ordered pair consisting of two adjacent vertices is called an arc. An edge connecting two vertices in a graph is often denoted by {u, w}, and this edge corresponds to two arcs (u, w) and (w, u).

Definition 2.3　The automorphism of a graph \mathrm{\Gamma }=(V,E) is a permutation of V keeping the adjacent relations of Γ unchanged, and the group formed all the automorphisms of Γ is called the automorphism group of Γ, denoted by \mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right). Γ is said to be a vertex-transitive, edge-transitive, or arc-transitive graph if \mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right) acts transitively on the vertex set, edge set, or arc set of Γ, respectively. Moreover, the graph Γ will be a G-vertex-transitive, G-edge-transitive, or G-arc-transitive graph if there exists G\le \mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right) acting transitively on the vertex set, edge set, or arc set of Γ, respectively.

Definition 2.4　Let Γ be a graph with V as the vertex set, E as edge set, and A as the arc set. The number of vertices contained in Γ is called the order of Γ, denoted by |V|. For any vertex v in Γ, Γ(v) stands for the set of all vertices adjacent to v in Γ, called the neighbor of v. The order of Γ(v) is said to be the degree of v.

Definition 2.5　A directed graph Γ is called a connected graph if for any two vertices v and w in Γ, there exists at least one path from v to w.

2.2 Cayley graphs and normal edge-transitive Cayley graphs

The following shows some related knowledge and well-known results of Cayley graphs and normal edge-transitive Cayley graphs.

Proposition 2.1 [8, 11]　 Let G be a group and S be its nonempty subset. Assuming that \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a Cayley graph of group G on its subset S.

(1) Graph Γ does not contain a self-loop if and only if S does not contain an identity element;

(2) Graph Γ is undirected if and only if S=S^{-1}:=\{s^{-1}\mid s\in S\};

(3) Graph Γ is connected if and only if G=⟨S⟩.

For any group G, symmetric group Sym(G) contains two regular subgroups \hat{G} and \check{G}. Here,

\check{G}=\left\{\check{g}:g\mapsto g^{-1}x,\mathrm{\forall }x\in G|g\in G\right\},

which contains the left multiplication of all elements in G. While

\hat{G}=\{\hat{g}:g\mapsto xg,\mathrm{\forall }x\in G|g\in G\},

which contains the right multiplication of all elements in G.

For any non-empty subset S of group G, let

\mathrm{A}\mathrm{u}\mathrm{t}(G,S)=\{\sigma \in \mathrm{A}\mathrm{u}\mathrm{t}(G\left)\right|S^{\sigma }=S\}.

\mathrm{A}\mathrm{u}\mathrm{t}(G,S)\le \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right)\le \mathrm{S}\mathrm{y}\mathrm{m}\left(G\right). As one of the subgroups of \mathrm{S}\mathrm{y}\mathrm{m}\left(G\right), \mathrm{A}\mathrm{u}\mathrm{t}(G,S) normalizes \hat{G}.

Cayley graph \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) must be a vertex-transitive graph since \hat{G}\le \mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right)and \hat{G} regularly act on the vertex set G. It can be known that

N_{\text{Aut}\left(\mathrm{\Gamma }\right)}(\hat{G})=\hat{G}⋊\text{Aut}(G,S).

The subgroup Aut(G, S) is of great significance in the study of normal Cayley graphs.

Definition 2.6　Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be the Cayley graph of group G with respect to its subset S. If N_{\mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right)}(\hat{G}) acts transitively on the edge set (arc set) of Γ, Γ will be called a normal edge-transitive (arc-transitive) Cayley graph.

Definition 2.7　Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be the Cayley graph of group G with respect to its subset S. If Γ is normal edge-transitive but not normal arc-transitive, Γ will be called a normal \frac{1}{2}-arc-transitive graph.

The following results have been proved in [8] and [14].

Proposition 2.2 [8, 14]　 Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be the Cayley graph of group G with respect to its subset S. The following conclusion is drawn:

(1) N_{\mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right)}\left(R\right(G\left)\right)=R\left(G\right)⋊\mathrm{A}\mathrm{u}\mathrm{t}(G,S);

(2) R\left(G\right)⊴\mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right) if and only if \mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right)=R\left(G\right)⋊\mathrm{A}\mathrm{u}\mathrm{t}(G,S)；

(3) Γ is normal if and only if A_1=\mathrm{A}\mathrm{u}\mathrm{t}(G,S). A₁ refers to the point stabilizer of the identity element in \mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{\Gamma }\right) of group G.

The following results are very meaningful for our work.

Proposition 2.3 [11]　 Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be an undirected connected Cayley graph of group G with respect to its subset S. Then Γ will be a normal edge-transitive Cayley graph if and only if \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S, or acts on S with two orbits T and T^{-1}, where T refers to a nonempty subset of S such that S=T\cup T^{-1}.

\mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts on S, and the elements in each orbit have the same order, so the following proposition holds.

Proposition 2.4 [5]　 Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be the Cayley graph of group G with respect to its subset S, and H be the set formed by all the second-order elements in G. If ⟨H⟩\ne G and Γ is a connected normal edge-transitive Cayley graph, then the degree of Γ will be even.

The following propositions are very meaningful for our work.

Proposition 2.5 [9]　 Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be an undirected connected Cayley graph of group G with respect to its subset S. Then Γ will be a normal arc-transitive Cayley graph if and only if \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S.

The following shows another result proposed in [5].

Proposition 2.6 [5]　 If S is a generating subset of G, then \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts faithfully on S.

3 Proof of the main theorems

Let p be an odd prime. The structure of non-abelian groups with order 2p² is clear. There are three kinds of structures as shown in [4].

\begin{array}{rl}& G_1\left(p\right)=⟨a,b\mid a^{p^2}=b^2=1,bab=a^{-1}⟩;\\ & G_2\left(p\right)=⟨a,b,c|a^p=b^p=c^2=[a,b]=1,cac=a^{-1},cbc=b^{-1}⟩;\\ & G_3\left(p\right)=⟨a,b,c\mid a^p=b^p=c^2=[a,b]=1,cac=a,cbc=b^{-1}⟩.\end{array}

In this paper, we discuss the conditions when G\cong G_3\left(p\right), namely the structure of group G is given by the following formula:

G=⟨a,b,c|a^p=b^p=c^2=[a,b]=1,c^{-1}ac=a,c^{-1}bc=b^{-1}⟩.

According to the definition, the elements in group G can be written in the form of a^i{b}^j{c}^k, where . From this, we can get the distribution of elements (except the identity element) in G as follows:

In the following, several lemmas are used to prove the main theorems. We first show the automorphism group of G.

Lemma 3.1　 \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right)=⟨f_{i,j,k}\mid f_{i,j,k}\left(a\right)=a^i,f_{i,j,k}\left(b\right)=b^j,f_{i,j,k}\left(c\right)=b^{k}c⟩, where .

Proof　If map f:\{a,b,c\}\to G is an automorphism of G, f\left(a\right),f\left(b\right),f\left(c\right) satisfy the relation of elements a, b, and c in group G, namelyf\left(a\right)f\left(b\right)=f\left(b\right)f\left(a\right),f\left(a\right)f\left(c\right)=f\left(c\right)f\left(a\right),f(c-1)f\left(b\right)f\left(c\right)=f(b-1). On the other hand, f\left(a\right),f\left(b\right),f\left(c\right) can generate G.

As \left|a\right|=\left|b\right|=\mathrm{p}, \left|c\right|=2, and all automorphisms on G are of the same order, f\left(a\right),f\left(b\right),f\left(c\right) can be the same order as a, b, c, respectively, and\left|f\right(a\left)\right|=\left|f\right(b\left)\right|=p,\left|f\right(c\left)\right|=2. It is known from Tab.1 that \left|a^i{b}^j\right|=p, 1\le i, , \left|b^{k}c\right|=2, in group G.

Next, we will discuss the automorphism f of group G.

Let f_{i,j,k,l,m}\left(a\right)=a^i{b}^j,f_{i,j,k,l,m}\left(b\right)=a^k{b}^l,f_{i,j,k,l,m}\left(c\right)=b^{m}c, where . i, j cannot be zero at the same time, and k, l cannot be zero at the same time. There will be

\begin{array}{rl}& f\left(a\right)f\left(c\right)=a^i{b}^j{b}^{m}c=a^i{b}^{j+m}c,\\ & f\left(c\right)f\left(a\right)=b^{m}c{a}^i{b}^j=a^i{b}^{m-j}c.\end{array}

If f\left(a\right)f\left(\mathrm{c}\right)=f\left(c\right)f\left(a\right), then b^{2j}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), and j=0. Since

\begin{array}{rl}& f\left(c^{-1}\right)f\left(b\right)f\left(c\right)=f\left(b^{-1}\right),\\ & f\left(c^{-1}\right)f\left(b\right)f\left(c\right)=(b^{m}c{)}^{-1}{a}^k{b}^l{b}^{m}c=a^k{b}^{-l},\\ & f\left(b^{-1}\right)={\left(a^k{b}^l\right)}^{-1}=a^{-k}{b}^{-l},\end{array}

a^{2k}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), and k=0. As a result,

f_{i,j,k,l,m}\left(a\right)=a^i,f_{i,j,k,l,m}\left(b\right)=b^l,f_{i,j,k,l,m}\left(c\right)=b^{m}c,

which satisfies

f\left(a\right)f\left(b\right)=a^i{b}^l=f\left(b\right)f\left(a\right).

Therefore, \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right)=⟨f_{i,j,k}\mid f_{i,j,k}\left(a\right)=a^i,f_{i,j,k}\left(b\right)=b^j,f_{i,j,k}\left(c\right)=b^{k}c⟩, where.

For the automorphism group of non-abelian group G with order 2p² under type G₃(p), the following results are obtained.

Proposition 3.1　 \left|\mathrm{A}\mathrm{u}\mathrm{t}\right(G\left)\right|=p(p-1{)}^2.

Proof　It is known from Lemma 3.1 that f_{i,j,k}\in \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right) if and only iff_{i,j,k}\left(a\right)=a^i, f_{i,j,k}\left(b\right)=b^j, f_{i,j,k}\left(c\right)=b^{k}c, where . Therefore, f_i,j,k defines all the elements in \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right) , and \left|\mathrm{A}\mathrm{u}\mathrm{t}\right(G\left)\right|=p(p-1{)}^2.

Proposition 3.2　 \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right)\cong ({\mathbb{Z}}_p⋊{\mathbb{Z}}_{p-1})\times {\mathbb{Z}}_{p-1}. The orbit of \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right) acting on G is: .

Proof　 \mathrm{\forall }{f}_{i,j,k}\in \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right), and f_{i,j,k}\left(a\right)=a^i, f_{i,j,k}\left(b\right)=b^k,f_{i,j,k}\left(c\right)=b^{j}c, where . From f_{i,j,k}\circ f_{i^{\prime },j^{\prime },k^{\prime }}=f_{i{i}^{\prime },k{j}^{\prime }+j,k{k}^{\prime }}, f_{i,j,k}^{-1}=f_{i_0,-k_{0}j,k_0}, where i{i}_0\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), k{k}_0\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right). Next, the 3×3 order matrix is defined as follows:

It is obvious \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right)\cong G.

Let set

Then A, B, C are all the subgroups of \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right), and the 3×3 order matrices corresponding to A, B, C are as follows:

On the one hand, C^{\prime }=A^{\prime }\cdot B^{\prime }, A^{\prime }\cap B^{\prime } is a unit matrix. On the other hand, \mathrm{\forall }c\in C^{\prime }, a\in A^{\prime }, and c^{-1}ac\in A^{\prime }. Therefore, A^{\prime }⊴C^{\prime }, and C^{\prime }=A^{\prime }⋊B^{\prime }\cong {\mathbb{Z}}_p⋊{\mathbb{Z}}_{p-1}.

Let set , and D\le \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right). The 3×3 order matrix corresponding to D is as follows:

It is obvious G=C^{\prime }\cdot D^{\prime }. C^{\prime }\cap D^{\prime } is a unit matrix. \mathrm{\forall }g\in G, c\in C^{\prime },d\in D^{\prime }, and g^{-1}cg\in C^{\prime }, g^{-1}dg\in D^{\prime }. As a result, C^{\prime }⊴G, D^{\prime }⊴G, and G=C^{\prime }\times D^{\prime }\cong ({\mathbb{Z}}_p⋊{\mathbb{Z}}_p-1)\times {\mathbb{Z}}_p-1. The proposition is proved.

Lemma 3.2　 Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be a connected normal edge-transitive Cayley graph of G with respect to its subset S. Then S is composed of elements with order 2p. \left|S\right| is even, and \left|S\right|>2.

Proof　If \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a connected normal edge-transitive Cayley graph, it can be seen from Proposition 2.3 that the elements in S have the same order. It is known from Tab.1 that the order of elements (except identity elements) in G is 2, p, or 2p. Since \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) is connected if and only if ⟨S⟩=G, S is composed of elements with order 2p.

If there are 2-order elements in S, it can be seen from Tab.1 that the 2-order elements in G are , which cannot generate a. Then ⟨S⟩\ne G, and S does not contain 2-order elements.

If there are elements with order p in S, it is known from Tab.1 that the elements with order p in G are , which cannot generate element c. At this time, ⟨S⟩\ne G, and S does not contain elements with order p.

Therefore, S contains only 2p-order elements. According to Proposition 2.4, |S| is even, and |S|>2. □

Lemma 3.3　 If p is an odd prime, can generate G if and only if j\not\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right).

Proof　 , there is (a^i{b}^{j}c{)}^{-1}=a^{-i}{b}^{j}c, (a^i{b}^{j}c{)}^2=a^{2i}. Since |a|=p, a\in ⟨S⟩. When j\not\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), there is \left(a^i{b}^{j}c\right)\cdot a^{-i}{b}^{l}c=b^{j-l}, and |b|=p. As a result, b\in ⟨S⟩. Since a^{-i}{b}^{-j}\cdot a^i{b}^{j}c=c, c\in ⟨S⟩. At this time, ⟨S⟩=G. Therefore, the lemma is proved.

Next, we prove Theorem 1.1.

Proof of Theorem 1.1　Sufficiency. It can be seen from Lemma 3.2 that \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a connected normal edge-transitive Cayley graph, then S is composed of elements with order 2p. Let S_1=\left\{ac,a^{-1}c,abc,a^{-1}bc\right\} and A_1=\mathrm{A}\mathrm{u}\mathrm{t}(G,S_1). It can be seen from Proposition 2.6 that A₁ acts faithfully on S_1. A_1\le S_4, and A₁ does not contain 3-order or 4-order elements.

If there is a 3-order element in A₁, let f_1\in A_1 with \left|f_1\right|=3, then f_1 can stabilize an element in S_1. If x\in S_1, then f_1\left(x\right)=x, which contradicts f₁ being a 3-order element.

If there is a 4-order element in A₁, let f_2\in A_1 with \left|f_2\right|=4, then f_2=\left(xy{x}^{-1}{y}^{-1}\right)or{f}_2=\left(x{y}^{-1}{x}^{-1}y\right), where x=ac,x^{-1}=a^{-1}c,y=abc,y^{-1}=a^{-1}bc. Let f_2=f_{r,s,t}, f_2\left(a\right)=a^r,f_2\left(b\right)=b^s,f_2\left(c\right)=b^{m}c. Two cases of f_2 are discussed below.

Case 1　When f_2=\left(xy{x}^{-1}{y}^{-1}\right), there is f_2\left(x\right)=f_2\left(ac\right)=a^r{b}^{m}c=y=abc. As a result, r\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right) and m\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right). Sincef_2\left(y\right)=f_2\left(abc\right)=a^r{b}^{s+m}c=x^{-1}=a^{-1}c, then r\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), which is contradictory.

Case 2　When f_2=\left(x{y}^{-1}{x}^{-1}y\right), there is f_2\left(x\right)=f_2\left(ac\right)=a^r{b}^{m}c=y^{-1}=a^{-1}bc. As a result, r\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right) and m\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right). Since f_2\left(y^{-1}\right)=f_2\left(a^{-1}bc\right)=a^{-r}{b}^{s+m}c=x^{-1}=a^{-1}c, which is also contradictory. Therefore, A₁ doesn’t contain 4-order elements.

Let f_{-1,1,0},f_{-1,-1,1},and{f}_{1,-1,1}\in \mathrm{A}\mathrm{u}\mathrm{t}(G,S_1). After calculations, we find that f_{-1,1,0}\left(x\right)=x^{-1}, f_{-1,-1,1}\left(x\right)=y^{-1}, f_{1,-1,1}\left(x\right)=y, and \left|f_{-1,1,0}\right|=\left|f_{-1,-1,1}\right|=\left|f_{1,-1,1}\right|=2. Therefore, A_1=\mathrm{A}\mathrm{u}\mathrm{t}\left(G,S_1\right) acts transitively on S₁, and \mathrm{C}\mathrm{a}\mathrm{y}(G,S_1) is a normal edge-transitive Cayley graph. There are at least three 2-order elements in A₁, so \mathrm{A}\mathrm{u}\mathrm{t}\left(G,S_1\right)\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2. Sincef_{i,l-j,j}\in \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right), , j\not\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right),f_{i,l-j,j}\left(S_1\right)=\{a^i{b}^{j}c,a^{-i}{b}^{j}c,a^i{b}^{l}c,a^{-i}{b}^{l}c\}=S. Similarly, we can obtain that \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a connected normal edge-transitive Cayley graph.

Necessity. Let set S=\{x,x^{-1},y,y^{-1}\}, \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) is connected if and only if ⟨S⟩=G. It can be known from Lemma 3. 3 that S can generate G if and only if .

If x=a^i{b}^{j}c, then y=a^k{b}^{l}c. It can be seen from Proposition 2.3 that \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a connected normal edge-transitive Cayley graph. \mathrm{A}\mathrm{u}\mathrm{t}(G,S) either acts on S transitively or with two orbits. S=T\cup T^{-1} and T is a non-empty set. If \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts on S with two orbits, S=T\cup T^{-1}, then T=\{x,y\} or T=\{x,y^{-1}\}, but f_{-1,1,0}\in \mathrm{A}\mathrm{u}\mathrm{t}\left(G,S\right) and f_{-1,1,0}\left(T\right)=T^{-1}. Therefore, \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S. There exists f=f_{t,n,q}\in \mathrm{A}\mathrm{u}\mathrm{t}(G,S) such that f\left(x\right)=y and f\left(y\right)=x, or x^{-1}, or y^{-1}. Three cases of f are discussed below.

Case 1　When f\left(x\right)=y and f\left(y\right)=x^{-1},there are

\begin{array}{rl}& f\left(x\right)=f\left(a^i{b}^{j}c\right)=a^{it}{b}^{nj+q}c=y=a^k{b}^{l}c,\\ & f\left(y\right)=f\left(a^k{b}^{l}c\right)=a^{tk}{b}^{nl+q}c=x^{-1}=a^{-i}{b}^{j}c.\end{array}

So, it\equiv k\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), tk\equiv -i\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), nj+q\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), nl+q\equiv j\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right). Let’s discuss the solution of these congruence equations:

(i) If p\equiv 3\left(\mathrm{m}\mathrm{o}\mathrm{d}4\right), then t^2\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), and there is no solution.

(ii) If p\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}4\right),, , and j\not\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right). Although t^2\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)has a solution, when q=0, there are n^2\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right) and j\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), which are contradictory.

Case 2　When f\left(x\right)=y,f\left(y\right)=y^{-1}, there are

\begin{array}{rl}& f\left(x\right)=f\left(a^i{b}^{j}c\right)=a^{it}{b}^{nj+q}c=y=a^k{b}^{l}c,\\ & f\left(y\right)=f\left(a^k{b}^{l}c\right)=a^{tk}{b}^{nl+q}c=y^{-1}=a^{-k}{b}^{l}c.\end{array}

So, it\equiv k\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), tk\equiv -k\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right),nj+q\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), nl+q\equiv j\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right). As ,, and j\not\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), there is i\equiv -k\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), and when q=0, there are n^2\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right) and j\equiv l\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), which are contradictory.

Case 3　When f\left(x\right)=y,f\left(y\right)=x, there are

\begin{array}{rl}& f\left(x\right)=f\left(a^i{b}^{j}c\right)=a^{it}{b}^{nj+q}c=y=a^k{b}^{l}c,\\ & f\left(y\right)=f\left(a^k{b}^{l}c\right)=a^{tk}{b}^{nl+q}c=x=a^i{b}^{j}c.\end{array}

So, it\equiv k\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), tk\equiv i\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), and p\left|\right(i-k\left)\right(t+1). As , i\equiv k\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), or t\equiv -1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right). At this time, S=\{a^i{b}^{j}c,a^{-i}{b}^{j}c,a^i{b}^{l}c,a^{-i}{b}^{l}c\}.

In summary, Theorem 1.1 is proved. At this time, \mathrm{A}\mathrm{u}\mathrm{t}(G,S)\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2.

Theorems 1.2 and 1.3 show some results of normal edge-transitive Cayley graphs on group G, which are proved as follows.

Proof of Theorem 1.2　Let \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) be a connected normal edge-transitive Cayley graph. It is known from Proposition 2.4 that the degree of Γ is even, and \left|\mathrm{\Gamma }\right(\alpha \left)\right|>2. From Lemma 3.2 and Lemma 3.3, we can see that , and S=S^{-1}. From Proposition 2.3, it is known that Γ is a connected normal edge-transitive Cayley graph, and then \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S or with two orbits. S=T\cup T^{-1}, where T refers to a nonempty set. Since \mathrm{\forall }{a}^i{b}^{j}c\in S, , f_{-1,1,0}\in \mathrm{A}\mathrm{u}\mathrm{t}(G,S), there is f_{-1,1,0}\left(a^i{b}^{j}c\right)=a^{-i}{b}^{j}c. As a result, a^i{b}^{j}c and a^{-i}{b}^{j}c both belong to the same orbit, which contradicts S=T\cup T^{-1}. Therefore, \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S. In addition, from Proposition 2.5 we can see that Γ is a G-arc-transitive graph.

Corollary 3.1　If Γ is a normal edge-transitive Cayley graph on group G, then Γ will not be a normal \frac{1}{2}-arc-transitive Cayley graph.

Example 3.1　Let G be a non-abelian group with order 2p² under type G₃(p). If , then \mathrm{\Gamma }=\mathrm{C}\mathrm{a}\mathrm{y}(G,S) will be a connected normal edge-transitive Cayley graph with degree p(p-1).

Proof of Theorem 1.3　It can be seen from Theorem 1.2 that , and Example 3.1 shows that if , then {\mathrm{\Gamma }}_1=\mathrm{C}\mathrm{a}\mathrm{y}(G,U) will be a connected normal edge-transitive Cayley graph, and \left|{\mathrm{\Gamma }}_1\right(\alpha \left)\right|=p(p-1).

Let , and Γ is a Cayley graph with degree 2d. Due to \mathrm{A}\mathrm{u}\mathrm{t}(G,S)\le \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right), it can be seen from Theorem 1.2 that \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S. As a result, 2d=\left|S\right|\mid \left|\mathrm{A}\mathrm{u}\mathrm{t}\right(G,S\left)\right|\mid \left|\mathrm{A}\mathrm{u}\mathrm{t}\right(G\left)\right|, and 2d\mid p(p-1{)}^2. As 2d\le p(p-1),d=p, or d\mid \frac{(p-1)}{2}, or d\nmid \frac{p-1}{2}, but \text{d}\mid p-1, or d\ne p and d\nmid \frac{p-1}{2}but d\mid \frac{(p-1)}{2}, or d\ne p and d\nmid p-1 but d\mid p(p-1), or d\nmid \frac{p-1}{2} and d\nmid p-1but d\mid \frac{(p-1{)}^2}{2}.

In order to prove the existence and uniqueness of the theorems, d is discussed in the following cases.

Case 1　Let d=p. Since f_{1,1,1}\in \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right),f_{1,1,1}\left(ac\right)=abc,f_{1,1,1}^2\left(ac\right)=a{b}^{2}c,f_{1,1,1}^3\left(ac\right)=a{b}^{3}c,\dots ,f_{1,1,1}^{p-1}\left(ac\right)=a{b}^{p-1}c, f_{1,1,1} can continuously act on ac to obtain setT=\{ac,abc,a{b}^{2}ca{b}^{3}c,\dots ,a{b}^{p-1}c\}, and\left|T\right|=p,f_{1,1,1}\left(T\right)=T.

Let T^{-1}=\left\{x^{-1}\right|x\in T\}=\{a^{-1}c,a^{-1}bc,a^{-1}{b}^{2}c,a^{-1}{b}^{3}c,\dots ,a^{-1}{b}^{p-1}c\}, S=T\cup T^{-1}. It can be seen from Theorem 1.2 that⟨S⟩=G. Sincef_{-1,1,0}\in \mathrm{A}\mathrm{u}\mathrm{t}(G,S), f_{-1,1,0}\left(T\right)=T^{-1}, \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S. Therefore, \mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a normal edge-transitive Cayley graph with degree 2p.

Case 2　If d\mid \frac{p-1}{2}, and the subgroup is formed by the point stabilizers of a, c under A=\mathrm{A}\mathrm{u}\mathrm{t}\left(G\right) and i is even, then {\overline{A}}_{a,c}\cong U_{\frac{p-1}{2}}. Let m be the generator of U_{\frac{p-1}{2}}. As a result, {\overline{A}}_{a,c}=⟨f_{1,m,0}⟩. Since d\mid \frac{p-1}{2}, there is a unique subgroup with order d in group U_{\frac{p-1}{2}}.

Let n=m^{\frac{p-1}{2d}}, and ⟨f_{1,n,0}⟩be a subgroup of {\overline{A}}_{a,c}, and |⟨f_{1,n,0}⟩|=d. Since f_{1,n,0}\in \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right), f_{1,n,0}\left(abc\right)=a{b}^{n}c,f_{1,n,0}^2\left(abc\right)=a{b}^{n^2}c,\dots ,f_{1,n,0}^{d-1}\left(abc\right)=a{b}^{n^{d-1}}c,f_{1,n,0} can continuously act on abc to obtain set T=\{abc,a{b}^{n}c,a{b}^{n^2}c,\dots ,a{b}^{n^{d-1}}c\}, and |T|=d, f_{1,n,0}\left(T\right)=T.

Let T^{-1}=\left\{x^{-1}\right|x\in T\}, S=T\cup T^{-1}. It can be seen from Theorem 1.2 that⟨S⟩=G. Since f_{-1,1,0}\in \mathrm{A}\mathrm{u}\mathrm{t}(G,S), f_{-1,1,0}\left(T\right)=T^{-1}, \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S. Therefore, \mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a normal edge-transitive Cayley graph with degree 2d.

Case 3　If d\nmid \frac{p-1}{2} but d\mid p-1, the group is formed by the point stabilizers of a and c under A=\mathrm{A}\mathrm{u}\mathrm{t}\left(G\right), and A_{a,c}\cong U_p. Let t be the generator of U_p, and then \text{L}{A}_{a,c}=⟨f_{1,t,0}⟩. Due to d\mid p-1, there is a unique subgroup with order d in group U_p.

Let \begin{array}{ccc}u& =& t^{\frac{p-1}{d}}\end{array}, then ⟨f_{1,u,0}⟩is a subgroup of A_a,c, and |⟨f_{1,u,0}⟩|=d. Since f_{1,u,0}\in \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right), f_{1,u,0}\left(abc\right)=a{b}^{u}c, f_{1,u,0}^2\left(abc\right)=a{b}^{u^2}c, f_{1,u,0}^3\left(abc\right)=a{b}^{u^3}c,\dots ,f_{1,u,0}^{d-1}\left(abc\right)=a{b}^{u^{d-1}}c. f_{1,u,0}can continuously act on abc to obtain set T=\{abc,a{b}^{u}c,a{b}^{u^2}c,\dots ,a{b}^{u^{d-1}}c\}, and \left|T\right|=d, f_{1,u,0}\left(T\right)=T.

Let T^{-1}=\left\{x^{-1}\right|x\in T\}=\{a^{-1}bc,a^{-1}{b}^{u}c,a^{-1}{b}^{u^2}c,\dots ,a^{-1}{b}^{u^{d-1}}c\}, S=T\cup T^{-1}. It can be seen from Theorem 1.2 that ⟨S⟩=G. As f_{-1,1,0}\in \mathrm{A}\mathrm{u}\mathrm{t}(G,S), f_{-1,1,0}\left(T\right)=T^{-1}, \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S. Therefore, Cay(G, S) is a normal edge-transitive Cayley graph with degree 2d.

At this time, \mathrm{A}\mathrm{u}\mathrm{t}\left(\mathrm{C}\mathrm{a}\mathrm{y}\right(G,S\left)\right)=⟨f_{1,u,0},f_{-1,1,0}⟩\cong {\mathbb{Z}}_d\times {\mathbb{Z}}_2.

The following discusses d\mid p(p-1) in different cases.

Case 4　(i) If 2d=p(p-1), then as mentioned above, \mathrm{C}\mathrm{a}\mathrm{y}(G,U) is the only maximal normal edge-transitive Cayley graph with degreep(p-1).

(ii) If d\ne p,d\nmid p-1, but d\mid p(p-1), then there exists t such that d=tp,t|p-1.

Let , then E\le \mathrm{A}\mathrm{u}\mathrm{t}\left(G\right).f_{u,1,i} can continuously act on ac to obtain set T=\{ac,a^{u}c,\dots ,a^{u^{t-1}}c,abc,a^{u}bc,a^{u^2}bc,\dots ,a^{u^{t-1}}bc,\dots ,a^{u^{t-1}}{b}^{p-1}c\}, and \left|T\right|=d,E\left(T\right)=T.

Let T^{-1}=\left\{x^{-1}\right|x\in T\}, S=T\cup T^{-1}. It is known that ⟨S⟩=G, and \mathrm{A}\mathrm{u}\mathrm{t}(G,S) acts transitively on S. Therefore, \mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a normal edge-transitive Cayley graph.

Case 5　If d\nmid \frac{(p-1)}{2} , and d\nmid p-1, but d\mid \frac{(p-1{)}^2}{2}, then there exist m and n such that d=mn,m\mid \frac{p-1}{2}, n\mid p-1.

Let H=⟨f_{s,1,0},f_{1,t,0}⟩, where s^n\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right), t=\frac{i}{2}, 1≤i<p, and i is even. t^m\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}\frac{p-1}{2}\right). H can continuously act on abc to obtain set T=\{abc,a^{s}bc,a^{s^2}bc,\dots ,a^{s^{n-1}}bc,a{b}^{t}c,a^s{b}^{t}c,a^{s^2}{b}^{t}c,\dots ,a^{s^{n-1}}{b}^{t}c,\dots ,a{b}^{t^{m-1}}c,a^s{b}^{t^{m-1}}c,\dots ,a^{s^{n-1}}{b}^{t^{m-1}}c\} and \left|T\right|=nm=d, H(T)=T. Let T^{-1}=\left\{x^{-1}\right|x\in T\}, S=T\cup T^{-1}. We can see that ⟨S⟩=G, Aut(G,S) acts transitively on S. Therefore, \mathrm{C}\mathrm{a}\mathrm{y}(G,S) is a normal edge-transitive Cayley graph with degree 2d.

In summary, the theorems are proved. □

References

[1] Alaeiyan M. On normal edge-transitive Cayley graphs of some Abelian groups. Southeast Asian Bull Math 2009; 33(1): 13–19

[2] BiggsN. Algebraic Graph Theory, 2nd ed. Cambridge Mathematical Library. Cambridge: Cambridge University Press, 1993

[3] Corr B P, Praeger C E. Normal edge-transitive Cayley graphs of Frobenius groups. J Algebraic Combin 2015; 42(3): 803–827

[4] Cui L, Zhou J X, Ghasemi M, Talebi A A. A classification of tetravalent non-normal Cayley graphs of order twice a prime square. J Algebraic Combin 2021; 53(3): 663–676

[5] Darafsheh M R, Assari A. Normal edge-transitive Cayley graphs on non-abelian groups of order 4p, where p is a prime number. Sci China Math 2013; 56(1): 213–219

[6] DixonJ DMortimerB. Permutation Groups, Grad. Texts in Math, Vol 163. New York: Springer-Verlag, 1996

[7] Fang X G, Li C H, Xu M Y. On edge-transitive Cayley graphs of valency four. European J Combin 2004; 25(7): 1107–1116

[8] Godsil C D. On the full automorphism group of a graph. Combinatorica 1981; 1(3): 243–256

[9] GodsilC DRoyleG. Algebraic Graph Theory. Grad Texts in Math, Vol 207. New York: Springer-Verlag, 2001

[10] Li C H, Lu Z P, Zhang H. Tetravalent edge-transitive Cayley graphs with odd number of vertices. J Combin Theory Ser B 2006; 96(1): 164–181

[11] Praeger C E. Finite normal edge-transitive Cayley graphs. Bull Austral Math Soc 1999; 60(2): 207–220

[12] Sharifi H, Darafsheh M R. On tetravalent normal edge-transitive Cayley graphs on the modular group. Turkish J Math 2017; 41(5): 1308–1312

[13] Talebi A A. Some normal edge-transitive Cayley graphs on dihedral groups. The Journal of Mathematics and Computer Science 2011; 2(3): 448–452

[14] Xu M Y. Automorphism groups and isomorphisms of Cayley digraphs. Discrete Math 1998; 182(1/2/3): 309–319

[15] XuM Y. Introduction to Finite Groups. Vol 1. Beijing: Science Press, 1999 (in Chinese)

RIGHTS & PERMISSIONS

Higher Education Press 2024