# Nonnormal Edge-Transitive Cubic Cayley Graphs of Dihedral Groups

Authors: Mehdi Alaeiyan; Siamak Firouzian; Mohsen Ghasemi
Journal: ISRN Algebra
 (2011)

---

## Abstract

A Cayley graph of a finite groupG is called normal edge transitive if its automorphism group has a subgroup which both normalizes G and acts transitively on edges. In this paper we determine all cubic, connected, and undirected edge-transitive Cayley graphs of dihedral groups, which are not normal edge transitive. This is a partial answer to the question of Praeger (1999).


---

## Body

## 1. Introduction

LetG be a finite group, and let S be a subset of G such that 1G∉S. The Cayley graphX= Cay(G,S) of G on S is defined as the graph with a vertex set V(X)=G and edge set E(X)={{g,sg}∣g∈G,s∈S}. Immediately from the definition there are three obvious facts (1) Aut(X), the automorphism group of X, contains the right regular representation R(G) of G; (2) X is connected if and only if G=〈S〉; (3) X is undirected if and only if S=S-1.A part ofAut(X) may be described in terms of automorphisms of G, that is, the normalizer NAut(X)(G)=G⋊Aut(G,S), a semidirect product of G by Aut(G,S), where Aut(G,S)={σ∈Aut(G)∣Sσ=S}.We simply useA(X) to denote the arc set of X. A Cayley graph X= Cay(G,S) is said to be vertex transitive, edge transitive, and arc transitive if its automorphism group Aut(X) is transitive on the vertex set V(X), edge set E(X), and arc set A(X), respectively. For s≥1, an s-arc in a graph X is an ordered (s+1)-tuple (v0,v1,…,vs) of vertices of X such that vi-1 is adjacent to vi for 1≤i≤s and vi-1≠vi+1 for 1≤i<s in other words, a directed walk of length s which never includes a backtracking. A graph X is said to be s arc transitive if Aut(X) is transitive on the set of s-arcs in X. In particular, 0 arc transitive means vertex transitive, and 1-arc transitive means arc transitive or symmetric. A subgroup of the automorphism group of a graph X is said to be s-regular if it acts regularly on the set of s-arcs of X.It is difficult to find the full automorphism group of a graph in general, and so this makes it difficult to decide whether it is edge-transitive, even for a Cayley graph. As an accessible kind of edge transitive graphs, Praeger [1] focuses attention on those graphs for which NAut(X)(G) is transitive on edges, and such a graph is said to be normal edge transitive. By the definition, every normal edge-transitive Cayley graph is edge-transitive, but not every edge-transitive Cayley graph is normal edge-transitive.Independently for our investigation, and as another attempt to study the structure of finite Cayley graphs, Xu [2] defined a Cayley graph X= Cay(G,S) to be normal if R(G) is normal subgroup of the full automorphism group Aut(X). Xu's concept of normality for a Cayley graph is a very strong condition. For example, Kn is normal if and only if n<4. However any edge-transitive Cayley graph which is normal, in the sense of Xu's definition, is automatically normal edge transitive.Praeger posed the following question in [1]: what can be said about the structure of Cayley graphs which are edge transitive but not normal edge transitive? In [3], Alaeiyan et al. have given partial answer to this question for abelian groups of valency at most 5, and also Sim and Kim [4] determined normal edge-transitive circulant graphs. In the next theorem we will identify all cubic edge transitive Cayley graphs of dihedral group which are not normal edge-transitive. This is a partial answer to Question 5 of [1]. Throughout of this paper, we suppose that D2n=〈a,b∣an=b2=1,bab-1=a-1〉, and X= Cay(D2n,S) is connected and undirected cubic Cayley graph. The main result of this paper is the following theorem.Theorem 1.1.
LetG=D2n be a dihedral group, and let  X= Cay(G,S) be a connected cubic Cayley graph. If  X is an edge-transitive Cayley graph but is not normal edge transitive, then  X,  G satisfy one of the following: (1)
n=4, S={b,ab,a2b}, X≅K4,4-4K2;(2)
n=8, S={b,ab,a3b},  X≅P(8,3), the generalized Peterson graph.


## 2. Basic Facts

In this section we give some facts on Cayley graphs, which will be useful for our purpose. First we make some comments about the normalizerNAut(X)(G) of the regular subgroup G. As before, the normalizer of the regular subgroup G in the symmetric group Sym(G) is the holomorph of G, that is, the semidirect product G⋊Aut(G). Thus,(2.1)N(Aut(X))(G)=(G⋊Aut(G))∩Aut(X)=G⋊(Aut(G)∩Aut(X))=G⋊Aut(G,S).The following lemmas are basic for our purpose. Now we have the first lemma from [1].Lemma 2.1 (see [1, Proposition 1]).
LetX= Cay(G,S) be a Cayley graph for a finite group  G. Then  X is normal edge transitive if and only if  Aut(G,S) is either transitive on  S or has two orbits in  S which are inverse of each other.Lemma 2.2 (see [2, Proposition 1.5]).
LetX= Cay(G,S), and  A=Aut(X). Then  X is normal if and only if  A1=Aut(G,S), where  A1 is the stabilizer of 1 in  A.Lemma 2.3 (see [5, Lemma 4.4]).
All 1-regular cubic Cayley graphs on the dihedral groupD2n are normal.Lemma 2.4 (see [6, Lemma 3.2]).
LetΓ be a connected cubic graph on dihedral group  D2n, and let  B1 and  B2 be two orbits of  C=〈a〉. Also let  G* be the subgroup of  G fixing setwise  B1 and  B2, respectively. If  G* acts unfaithfully on one of  B1 and  B2, then  Γ≅K3,3.LetCG be the core of C=〈a〉 in Aut(X). By assuming the hypothesis in the above lemma, we have the following resultsLemma 2.5 (see [6, Lemma 3.5]).
IfCG is a proper subgroup of  C, then  X is isomorphic to  Cay(D14,{b,ab,a3b}) or  Cay(D16,{b,ab,a3b}).Lemma 2.6 (see [6, Lemma 3.6]).
IfCG=C, then  X is isomorphic to  Cay(D2n,{b,ab,akb}), where  k2-k+1=0 (mod  n), and  n≥13.LetG=D2n. Then the elements of G are ai and aib, where i=0,1,…,n-1. All aib are involutions, and ai is an involution if and only if n is even and i=n/2. Finally in this section we obtain a preliminary result restricting S for cubic Cayley graphs of Cay(D2n,S). We can easily prove the following lemmaLemma 2.7.
LetΓ= Cay (G,S) be  Cayley graphs of  G=D2n. Then  Γ is cubic, connected and, undirected if and only if one of the following conditions holds (1)
Whenn is odd, one has(2.2)So1={aib,ajb,akb},0≤i<j<k<n,So2={ai,a-i,ajb},0<i<n2,0≤j<n,(2)
Whenn is even, one has(2.3)Se1={aib,ajb,akb},0≤i<j<k<n,Se2={ai,a-i,ajb},0<i<n2,0≤j<n,Se3={an2,ai,a-i},0<i<n2,Se4={an/2,aib,ajb},0≤i<j<n.LetX and Y be two graphs. The direct productX×Y is defined as the graph with vertex set V(X×Y)=V(X)×V(Y) such that for any two vertices u=[x1,y1] and v=[x2,y2] in V(X×Y), [u,v] is an edge in X×Y whenever x1=x2 and [y1,y2]∈E(Y) or y1=y2 and [x1,x2]∈E(X). Two graphs are called relatively prime if they have no nontrivial common direct factor. The lexicographic productX[Y] is defined as the graph with vertex set V(X[Y])=V(X)×V(Y) such that for any two vertices u=[x1,y1] and v=[x2,y2] in V(X[Y]), [u,v] is an edge in X[Y] whenever [x1,x2]∈E(X) or x1=x2 and [y1,y2]∈E(Y). Let V(Y)={y1,y2,…,yn}. Then there is a natural embedding nX in X[Y], where for 1≤i≤n, the ith copy of X is the subgraph induced on the vertex subset {(x,yi)∣x∈V(X)} in X[Y]. The deleted lexicographic productX[Y]-nX is the graph obtained by deleting all the edges (natural embedding) of  nX from X[Y].


## 3. Proof of Theorem1.1

As we have seen in Section1, each edge transitive Cayley graph which is normal is automatically normal edge transitive. Hence for the proof of Theorem 1.1, we must determine all nonnormal connected undirected cubic Cayley graphs for dihedral group D2n. If n=2, then dihedral group D4 is isomorphic to ℤ2×ℤ2, and so it is easy to show that the cubic Cayley graph Cay(D4,S) is normal. So from now we assume that n≥3. Also, since Cay(D2n,S) when S=Se3 is disconnected, thus we do not consider this case for the proof of the main theorem. First we prove the following lemma.Lemma 3.1.
LetG be the dihedral group D2n with n≥3, and let Γ = Cay (G,S) be a cubic Cayley graph. Then(a)
ifS is Se4 and Γ is connected, then S∩(S2-{1})=∅ holds;(b)
ifS is So2 or Se2 and Γ is connected, then S∩(S2-{1})=∅ if n>3. For n=3, and S is So2 or Se2, one has; S∩(S2-{1})≠∅ and Γ=Cay(D6,S) is connected and normal;(c)
ifS is So1 or Se1, then S∩(S2-{1})=∅ always holds.Proof.
(a) Suppose first thatS=Se4={an/2,aib,ajb}. Then
(3.1)S2-{1}={an/2+ib,an/2+jb,ai-j,aj-i}.
We show that S∩(S2-{1})=∅. Suppose to the contrary that S∩(S2-{1})≠∅. We may suppose that ai-j=aj-i=an/2. Now we have Γ=nK1[Y], where Y=K4. Hence Γ is not connected, which is a contradiction.
(b) Now suppose thatS=So2 or  S=Se2, that is, S={ai,a-i,ajb}. For n>3, we have S2-{1}={a2i,a-2i,ai+jb,aj-ib}. We claim that S∩(S2-{1})=∅. Suppose to the contrary that S∩(S2-{1})≠∅. We may suppose that a2i=a-i. Then Γ=mK1[Y], where Y=Cay(S,〈S〉) and |D2n:〈S〉|=m. So Γ is not connected, which is a contradiction. Now let n=3. Then S={a,a-1,b}, {a,a-1,ab}, or {a,a-1,a2b}, respectively. Therefore S2-1={a2,ab,a2b,a}, {a2,a2b,a,b}, or {a2,b,a,ab}, respectively. Obviously Γ is connected, and G≅D6. Also we have S∩(S2-{1})≠∅, and Cay(D6,{a,a-1,b})≅  Cay(D6,{a,a-1,ab})≅ Cay(D6,{a,a-1,a2b}). Let σ be an automorphism of Γ=Cay(D6,{a,a-1,b}), which fixes 1 and all elements of S. Since aσ=a, and (a2)σ=a2, we have {1,a2,a2b}σ={1,a2,a2b} and {1,a,ab}σ={1,a,ab}. Therefore (ab)σ=ab, and (a2b)σ=a2b, and hence σ fixes all elements of S2. Thus σ=1, and A1 acts faithfully on S. So we may view A1 as a permutation group on S. Now let α be an arbitrary element of A1. Since 1α=1, we have {a,a2,b}α={a,a2,b}. If bα=a or bα=a2, then {1,ab,a2b}α={1,a2b,a2} or {1,ab,a2b}α={1,ab,a}, which is a contradiction. Thus bα=b, and A1 is generated by the permutation (a,a2). So |A1|=2. On the other hand, β:atbl→a2tbl is an element of Aut(G,S). Therefore |A1|=|Aut(G,S)|=2, and hence by Lemma 2.2, Γ is normal.
(c) Finally, suppose thatS=So1 or S=Se1, that is, S={aib,ajb,akb}. Then S2-{1}={ai-j,aj-i,ai-k,ak-i,aj-k,ak-j}. Clearly S∩(S2-{1})=∅. The results now follow.
By considering this lemma, we prove the following proposition. This result will be used in the proof of Theorem1.1.Proposition 3.2.
LetG be the dihedral group  D2n(n≥3), and let  X=Cay(G,S) be a connected and undirected cubic Cayley graph. Then  X is normal except y one of the following cases happens: (1)
n=4,S={b,ab,a2b},X≅K4,4-4K2;(2)
n=8,S={b,ab,a3b},X≅P(8,3), (the generalized Peterson graph);(3)
n=3,S={b,ab,a2b},X≅K3,3;(4)
n=7,S={b,ab,a3b},X≅S(7), (Heawood's graph).Proof.
First assume thatS=Se4. Since Γ is connected, by Lemma 3.1(a), S∩(S2-{1})=∅. Now consider the graph Γ2(1), and let σ be an automorphism of Γ=Cay(D2n,{an/2,aib,ajb}, which fixes 1 and all elements of S. Since (an/2)σ=an/2, (aib)σ=aib, and (ajb)σ=ajb, we have {1,an/2+ib,an/2+jb}σ={1,an/2+ib,an/2+jb},{1,an/2+ib,aj-i}σ={1,an/2+ib,aj-i}, and {1,an/2+jb,ai-j}σ={1,an/2+jb,ai-j}, respectively. Therefore (an/2+ib)σ=an/2+ib, (an/2+jb)σ=an/2+jb,(aj-i)σ=aj-i, and (ai-j)σ=ai-j, and hence σ fixes all elements of S2. Because of the connectivity of Γ, this automorphism is the identity in Aut(Γ). Therefore A1 acts faithfully on S. So we may view A1 as a permutation group on S. Now let α be an arbitrary element of A1. Since 1α=1, we have {an/2,aib,ajb}α={an/2,aib,ajb}. If (an/2)α=aib, or (an/2)α=ajb, then {1,an/2+ib,an/2+jb}α={1,an/2+ib,aj-i}, or {1,an/2+ib,an/2+jb}α={1,an/2+jb,ai-j}, respectively. Now again we consider Γ2(1). In this subgraph, an/2+ib and an/2+jb have valency 2, and ai-j, aj-i have valency 1. This implies a contradiction. Thus (an/2)α=an/2, and A1 is generated by the permutation (aib,ajb). So |A1|=2. On the other hand, β:atbl→a-t(ai+jb)l is an element of Aut(G,S). Therefore |A1|=|Aut(G,S)|=2, and hence by Lemma 2.2, Γ is normal.
Now assume thatS=Se2={ai,a-i,ajb}, or  S=So2={ai,a-i,ajb}. If n=3, then by Lemma 3.1 (b), Γ=Cay(D6,S), and Γ is normal. Now if n>3, then again by Lemma 3.1(b), S∩(S2-{1})=∅. Considering the graph Γ2(1), with the same reason as before if an automorphism of Γ fixes 1 and all elements of S, then it also fixes all elements of S2. Because of the connectivity of Γ, this automorphism is the identity in Aut(Γ). Therefore A1 acts faithfully on S. So we may view A1 as a permutation group on S. We can easily see that A1 is generated by the permutation (ai,a-i). So |A1|=2. On the other hand, σ:atbl→a-t(a2jb)l is an element of Aut(G,S). Therefore |A1|=|Aut(G,S)|=2, and hence by Lemma 2.2, Γ is normal.
Finally assume thatS=Se1={aib,ajb,akb}, or S=So1={aib,ajb,akb}. Up to graph isomorphism, S={b,ajb,akb}, where <j,k≥Zn*. In this case, Γ is a bipartite graph with the partition B=B1∪B2, where B1 and B2 are just two orbits of C=〈a〉, and we assume the block B1 contains 1. Let G* be the subgroup of G fixing setwise B1 and B2, respectively. If G* acts unfaithfully on one of B1 and B2, then by Lemma 2.4, Γ≅K3,3, and σ=(b,ab) is not in Aut(G,S) but in A1, and so Γ is not normal. Let G* act faithfully on B1 and B2. Then n≠3. If n=4, then Γ is isomorphic to K4,4-4K2, and σ=(b,ab)(a2,a3) is not in Aut(G,S) but in A1, and so Γ is not normal. From now on we assume n≥5. Now suppose that CG, the core of C in G, is a proper subgroup of C. Then by Lemma 2.5, Γ≅ Cay(D14,{b,ab,a3b}) or Γ≅ Cay(D16,{b,ab,a3b}). For the first case, σ=(a,a2,a3,a6)(a4,a5)(a2b,a6b,a5b,a4b)(ab,b) is not in Aut(G,S) but in A1, and so Γ is not normal. For the second case, σ=(a,a7,a6)(a2,a5,a3)(b,ab,a3b)(a4b,a5b,a7b) is not in Aut(G,S) but in A1, and so Γ is not normal. Finally we suppose that CG=C. Then by Lemma 2.6, Γ is isomorphic to the Cay(D2n,{b,ab,akb}), where k2-k+1≡0 (mod n) and n≥13. The Cayley graph Γ is 1-regular, and by Lemma 2.3, Γ is normal. The result now follows.
Now we complete the proof of Theorem1.1. We remind that any edge transitive Cayley graph which is normal, in the sense of Xu's definition, is also normal edge transitive. Thus this implies that we must consider nonnormal Cayley graphs which were obtained in Proposition 3.2. So we consider four cases in Proposition 3.2. For case (1), we claim that there is no automorphism of G such that b maps to ab. Suppose to the contrary that there is an automorphism σ such that b maps to ab. Then a must be mapped to ai, where (i,4)=1, and so with the simple check it is easy to see that this is a contradiction. Also in case (2), with the same reason as above there is a contradiction. Hence Aut(G,S) does not act transitively on S also does not have two orbits in S which are inverse of each other. Now by using Lemma 2.1 these graphs are not normal edge transitive. For the last two cases it is easy to show that Aut(G,S) acts transitively on S, and hence by Lemma 2.1, these graphs are normal edge transitive. Now the proof is complete as claimed.



---

*Source: 428959-2011-09-07.xml*