# Normal Edge-Transitive Cayley Graphs of the GroupU

Authors: A. Assari; F. Sheikhmiri
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

A Cayley graph of a groupG is called normal edge-transitive if the normalizer of the right representation of the group in the automorphism of the Cayley graph acts transitively on the set of edges of the graph. In this paper, we determine all connected normal edge-transitive Cayley graphs of the group U
6
n.


---

## Body

## 1. Introduction

LetG be a group and let S be a subset of G. The Cayley graph of G with respect to S is a graph with the group G as the vertex set and (
x
,
y
) is an arc of the graph, if and only if for some s
∈
S we have y
=
s
x. We denote the Cayley graph by Γ
=
Cay
(
G
,
S
). Since G is a group, the Cayley graph cannot have any parallel edges. In addition we assume that the subset S does not contain the identity element of the group G to avoid having loops in the Cayley graph and also to be an inverse closed set; that is, S
=
S
-
1, to have an undirected Cayley graph. Therefore, we focus on simple Cayley graphs.LetΓ
=
(
V
,
E
) be a simple graph with vertex set V and edge set E. In this paper, we denote the edge, joining the vertices x and y by {
x
,
y
}. An automorphism of the graph Γ is a permutation on the vertex set of Γ which preserves the edges. The set of all automorphisms of Γ forms a group with the composition of maps as the binary operation and is denoted by Aut
(
Γ
). Since Aut
(
Γ
) is a permutation group of V, it acts on V as well as E in the usual way. Γ is called vertex-transitive, edge-transitive, or arc-transitive, iff Aut
(
Γ
) acts transitively on the set of vertices, edges, or arcs of Γ, respectively. Γ is called half-arc-transitive iff it is vertex- and edge-transitive, but not arc-transitive.LetG be a finite group and let S be an inverse closed subset of G that does not contain the identity. Set Γ
=
Cay
(
G
,
S
). Γ is connected iff S is a generating set of the group G. For g
∈
G, define the mapping ρ
g
:
G
→
G by ρ
g
(
x
)
=
x
g, for all x
∈
G. ρ
g
∈
Aut
(
Γ
) for every g
∈
G, and hence R
(
G
)
=
{
ρ
g
∣
g
∈
G
} is a regular subgroup of Aut
(
Γ
) isomorphic to G, forcing Γ to be a vertex-transitive graph.LetAut
(
G
,
S
)
=
{
α
∈
Aut
(
G
)
∣
S
α
=
S
}. Normalizer of R
(
G
) in Aut
(
Γ
) is equal to
(1)
N
Aut
(
Γ
)
(
R
(
G
)
)
=
R
(
G
)
⋊
Aut
(
G
,
S
)
,
where ⋊ denotes the semidirect product of two groups [1].In [2], the graph Γ is called normal if R
(
G
) is a normal subgroup of Aut
(
Γ
). And after that the normality of Cayley graphs has been extensively studied from different points of view. Among them, finding and classifying the normal Cayley graphs were an essential problem, since in normal Cayley graphs we know the exact automorphism group of the graph.It was conjectured in [2] that most Cayley graphs are normal. For example, in [3] the authors determined all possible nonnormal (and, as a consequence, normal) Cayley graphs of groups of order 2
p
2, and lots of other authors have done similar works for groups of orders p, 2
p, 4
p, p
2, and p
q [4–8].Another concept which was similar to the above one is introduced by Praeger in [9] in which a Cayley graph Γ
=
Cay
(
G
,
S
) of a group G with respect to S is called normal edge-transitive or arc-transitive if N
Aut
(
Γ
)
(
R
(
G
)
) acts on the edges or arcs of  Γ, respectively, and it is called normal half-arc-transitive Cayley graph if it is normal edge-transitive Cayley graph which is not normal arc-transitive. Obviously, any normal edge-transitive Cayley graph is edge-transitive. Thus, this concept talks about the symmetric properties of a Cayley graph.The latter concepts also were considered very much in the literature. For example, Alaeiyan in [10] found a class of normal edge-transitive Cayley graphs of abelian groups or, in [11], authors found all normal edge-transitive Cayley graphs of order 4
p and as a consequence found a class of normal half-arc-transitive Cayley graphs which rarely happens. This motivated us to consider the Cayley graphs of groups U
6
n and classify all normal edge-transitive Cayley graphs of groups U
6
n.


## 2. Preliminary Results

One of the principle theorems that helps us to connect the group properties of a groupG and normal edge-transitivity of Γ
=
Cay
(
G
,
S
) is the following theorem which is proved in [9].Theorem 1.
LetΓ
=
C
a
y
(
G
,
S
) be a connected Cayley graph on S. Then, Γ is normal edge-transitive if and only if A
u
t
(
G
,
S
) is either transitive on S or has two orbits in S in the form of  T and T
-
1, where T is a nonempty subset of S such that S
=
T
∪
T
-
1.The following corollary comes from Theorem1 which is also mentioned in [11].Corollary 2.
LetΓ
=
C
a
y
(
G
,
S
) and let H be the subset of all involutions of the group G. If H does not generate the group G and Γ is connected normal edge-transitive, then the valency of Γ is even.Theorem1 with a result in [12] characterizes arc-transitive and half-arc-transitive Cayley graphs as described in the following.Theorem 3.
LetΓ
=
C
a
y
(
G
,
S
) be a connected normal edge-transitive Cayley graph. Γ is normal arc-transitive if A
u
t
(
G
,
S
) acts transitively on S and Γ is normal half-arc-transitive if S
=
T
∪
T
-
1, where T is an orbit of the action of A
u
t
(
G
,
S
) on S.


## 3. GroupU
6
n

GroupU
6
n has the presentation
(2)
U
6
n
=
〈
b
-
1
a
,
b
∣
a
2
n
=
b
3
=
1
,
a
-
1
b
a
=
b
-
1
〉
,
which we can write its elements as follows:
(3)
U
6
n
=
{
a
i
b
j
∣
0
⩽
i
⩽
2
n
-
1,0
⩽
j
⩽
2
}
.
One can see that the group U
6
n has order 6
n.In Theorem1, there are some relations between the normal edge-transitive Cayley graphs and the automorphism group of the relying group. Therefore, first we will find the automorphism group of the group U
6
n.Theorem 4.
Every automorphism of the groupU
6
n is in the form of σ
i
,
j
:
U
6
n
→
U
6
n which sends a to a
i and b to b
j, or δ
i
,
j
,
s
:
U
6
n
→
U
6
n sends a to a
i
b
j and b to b
s, where (
i
,
2
n
)
=
1 for 0
⩽
i
⩽
2
n
-
1 and 1
⩽
j,  s
⩽
2.Proof.
First of all we find some relations between elements of the groupU
6
n.
Sincea
-
1
b
a
=
b
-
1, equivalently
(4)
b
a
=
a
b
-
1
.
Hence, we have
(5)
b
2
a
=
b
b
a
=
b
a
b
2
=
a
b
2
b
2
=
a
b
.
One can check by induction that, for 0
⩽
i
⩽
2
n
-
1 and 1
⩽
j
⩽
2, we will have
(6)
b
j
a
i
=
{
a
i
b
j
if
i
is
even
;
a
i
b
-
j
if
i
is
odd
.
If we denote the order of element of x by o
(
x
), then, for 0
⩽
i
⩽
2
n
-
1, we have
(7)
o
(
a
i
)
=
2
n
(
i
,
2
n
)
.
For finding the order of elements of the forma
i
b
j for j
=
1,2, we have to observe that, for odd i and arbitrary k, we have (
a
i
b
)
2
k
=
a
2
i
k and (
a
i
b
)
2
k
+
1
=
a
i
(
2
k
+
1
)
b and, for even i and arbitrary k, we have (
a
i
b
)
3
k
=
a
3
i
k, (
a
i
b
)
3
k
+
1
=
a
i
(
3
k
+
1
)
b, and (
a
i
b
)
3
k
+
2
=
a
i
(
3
k
+
2
)
b
2 which can be obtained from (6).
Therefore, if the order ofx
=
a
i
b is L, for odd i, then L
=
2
k for some integer k. Since order of a is 2
n, we should have
(8)
2
n
∣
2
i
k
⟹
n
∣
i
k
⟹
n
(
n
,
i
)
∣
k
.
But k should be the least integer satisfying the condition and implies k
=
n
/
(
n
,
i
); that is,
(9)
o
(
a
i
b
)
=
2
n
(
n
,
i
)
,
if
i
is
odd
,
where (
·
,
·
) is the greatest common divisor.
Similar argument can apply fora
i
b
2 in the case i is odd to obtain
(10)
o
(
a
i
b
2
)
=
2
n
(
n
,
i
)
,
if
i
is
odd
.
Now for eveni, assume i
=
2
j for some integer j and o
(
a
i
b
)
=
L
=
3
k for some integer k. Thus, we have
(11)
(
a
i
b
)
3
k
=
(
a
2
j
b
)
3
k
=
a
6
j
k
=
1
.
Compare it with the order of a; we get
(12)
2
n
∣
6
j
k
⟹
n
∣
3
k
⟹
n
(
n
,
j
)
∣
3
k
.
Since 3
∣
3
k, one can conclude that [
n
/
(
n
,
j
)
,
3
]
∣
3
k, where [
·
,
·
] is the least common multiple, and finally we obtain
(13)
o
(
a
i
b
)
=
[
n
(
n
,
i
/
2
)
,
3
]
,
if
i
is
even
.
Similar argument can be discussed to prove
(14)
o
(
a
i
b
2
)
=
[
n
(
n
,
i
/
2
)
,
3
]
,
if
i
is
even
.
Suppose σ is an automorphism of the group U
6
n; thus, σ preserves the order of elements; hence, o
(
σ
(
a
)
)
=
o
(
a
)
=
2
n and o
(
σ
(
b
)
)
=
o
(
b
)
=
3.
By the order of elements ofU
6
n, if we define the following sets
(15)
A
=
{
a
i
(
i
,
2
n
)
=
1
}
,
B
=
{
a
i
b
j
(
i
,
2
n
)
=
1
}
(
observe
that
in
this
case
i
is
odd
)
C
=
{
a
2
n
/
3
,
a
4
n
/
3
}
,
D
=
{
a
2
r
b
s
r
=
n
3
,
2
n
3
,
s
=
1,2
}
,
E
=
{
b
,
b
2
}
,
by the order of elements of the group U
6
n, we can say that σ
(
a
)
∈
A
∪
B and σ
(
b
)
∈
C
∪
D
∪
E. Let x
=
σ
(
a
) and y
=
σ
(
b
). But all of the following cases which may happen for x and y yield a contradiction. (1)
x
∈
A and y
∈
C contradicts with the fact that {
σ
(
a
)
,
σ
(
b
)
} is a generating set of U
6
n.
(2)
x
∈
A and y
∈
D. The equation a
-
1
b
a
=
b
-
1 implies x
-
1
y
x
=
y
-
1 which also implies r
=
0 or r
=
n
/
2. But none of them can occur, since r
∈
{
n
/
3
,
2
n
/
3
}.
(3)
x
∈
B and y
∈
C. Thus, x
=
a
i
b
j for some odd i and y
=
a
r for some r
∈
{
2
n
/
3
,
4
n
/
3
}. Hence, r is even and r
+
i is odd and we have
(16)
x
-
1
y
x
=
a
-
i
b
j
a
r
a
i
b
j
=
a
r
.
But x
-
1
y
x
=
y
-
1
=
a
-
r because σ is an automorphism and hence a
r
=
a
-
4 yields r
=
n, which is a contradiction.
(4)
x
∈
B and y
∈
D. We can write x
=
a
i
b
j, for odd i, and y
=
a
2
r
b
s, for r
∈
{
n
/
3
,
2
n
/
3
} and 1
⩽
s
⩽
2. Thus, i and, hence, 2
r
+
i are odd and we obtain
(17)
x
-
1
y
x
=
a
-
i
b
j
a
2
r
b
s
a
i
b
j
=
a
-
i
b
j
a
2
r
+
i
b
-
s
+
j
=
a
-
i
+
2
r
+
i
b
-
j
-
s
+
j
=
a
2
r
b
-
s
.
But we have x
-
1
y
x
=
y
-
1
=
a
-
2
r
b
-
s. Thus, we should have a
2
r
=
a
-
2
r; that is, r
=
n
/
2, which is a contradiction.Therefore, the only cases that may happen are the cases x
∈
A, y
∈
E and x
∈
B, y
∈
E and the theorem is proved.And from Theorem4, we can obtain that the automorphism group of the group U
6
n is as follows:
(18)
Aut
(
U
6
n
)
=
{
σ
i
,
j
,
δ
i
,
j
,
s
:
U
6
n
⟶
U
6
n
∣
(
i
,
2
n
)
=
1
,
j
,
s
∈
{
1,2
}
,
k
k
k
k
k
k
k
σ
i
,
j
(
a
)
=
a
i
,
σ
i
,
j
(
b
)
=
b
j
,
δ
i
,
j
,
s
(
a
)
=
a
i
b
j
,
k
k
k
k
k
k
k
δ
i
,
j
,
s
(
b
)
=
b
s
}
.Now, we are ready to find the orbits of the groupU
6
n under the action of Aut
(
U
6
n
).Lemma 5.
In the action of groupA
u
t
(
U
6
n
) on U
6
n, each element falls into one of the following orbits, depending on k:(I)
{
a
k
i
∣
k
i
s
e
v
e
n
,
(
i
,
2
n
)
=
1
};
(II)
{
a
k
i
b
j
∣
k
i
s
e
v
e
n
,
1
⩽
j
⩽
2
};
(III)
{
a
k
i
b
j
∣
k
i
s
o
d
d
,
0
⩽
j
⩽
2
};
(IV)
{
b
,
b
2
}.Proof.
By Relation (6), one can show that, for odd i, if k is even, then (
a
i
b
j
)
k
=
a
k
i, and if k is odd, then (
a
i
b
j
)
k
=
a
k
i
b
j for 1
⩽
j
⩽
2. Therefore, images of elements of U
6
n under σ
i
,
j and δ
i
,
j
,
s in Aut
(
U
6
n
) are as follows (recall that (
i
,
2
n
)
=
1,1
⩽
j, s
⩽
2).
Ifk is even, then
(19)
σ
i
,
j
(
a
k
)
=
(
a
i
)
k
=
a
k
i
,
σ
i
,
j
(
a
k
b
l
)
=
(
a
i
)
k
(
b
j
)
l
=
a
k
i
b
l
j
,
ll
lllll
1
⩽
l
,
j
⩽
2
,
i
.
e
.
1
⩽
l
j
⩽
2
,
δ
i
,
j
,
s
(
a
k
)
=
(
a
i
b
j
)
k
=
a
k
i
,
δ
i
,
j
,
s
(
a
k
b
l
)
=
(
a
i
b
j
)
k
(
b
l
)
s
=
a
i
k
b
j
+
l
s
.
Ifk is even or odd, then σ
i
,
j
(
b
l
)
=
b
l
j and σ
i
,
j
,
s
(
b
l
)
=
b
l
s. Therefore, the orbit of a
k for an even k is {
a
k
i
∣
k
is
even
,
(
i
,
2
n
)
=
1
} and for odd k is {
a
k
i
b
j
∣
k
is
odd
,
0
⩽
j
⩽
2
}. The orbit of a
k
b
l for an even k is {
a
k
i
b
j
∣
k
is
even
,
1
⩽
j
⩽
2
} and for odd k is {
a
k
i
b
j
∣
k
is
odd
,
0
⩽
j
⩽
2
}. And finally the orbit of b is {
b
,
b
2
}.Now we bring a sufficient condition under which a Cayley graph of groupU
6
n can be normal edge-transitive.Theorem 6.
IfΓ
=
C
a
y
(
U
6
n
,
S
) is connected normal edge-transitive Cayley graph, then |
S
| is even, greater than 2, and S is contained in {
a
k
i
b
j
∣
k
i
s
o
d
d
,
0
⩽
j
⩽
2
}.Proof.
From Corollary2, |
S
| is even.
SinceΓ is normal edge-transitive, by Theorem 1, Aut
(
U
6
n
,
S
) acts transitively on S or S
=
T
∪
T
-
1 where T is an orbit of the action of Aut
(
U
6
n
,
S
). Since Aut
(
U
6
n
,
S
) is a subgroup of Aut
(
U
6
n
), thus S or, in the latter case, T should be contained in one of orbits of Aut
(
U
6
n
) on U
6
n. But, from Lemma 5, we have 4 kinds of orbits in this action. But from (6), if i and j are even, a
i
b
s
a
j
b
s
′
=
a
i
+
j
b
s
+
s
′. Thus, i
+
j is even and a is not generated by such elements. Therefore, if S is contained in an orbit of kind I, II, or IV, S will not generate U
6
n. Therefore, Γ will not be connected. Thus, S is contained in III.Theorem6 has a critical corollary.Corollary 7.
Γ
=
C
a
y
(
U
6
n
,
S
) is never connected normal half arc-transitive Cayley graph.Proof.
For oddi and 0
⩽
j
⩽
2, we have (
a
i
b
j
)
-
1
=
b
-
j
a
-
i
=
a
-
i
b
j. From Theorem 6, S contains such elements. Since S is closed under inversion, S is union of A
i
j
=
{
a
i
b
j
,
a
-
i
b
j
} for some odd i and some 0
⩽
j
⩽
2. σ
-
1,1 is an automorphism of G which preserves A
i
j, for all i and j, and hence preserves S; that is, σ
-
1,1
∈
Aut
(
G
,
S
). Accordingly, if we set S
=
T
∪
T
-
1, then each element of T is sent to an element of T
-
1 by σ
-
1,1. T is not an orbit of the action of Aut
(
G
,
S
) on S.By Theorems1 and 6 and Corollary 7 we can obtain the following theorem.Theorem 8.
Γ
=
C
a
y
(
U
6
n
,
S
) is connected normal edge-transitive Cayley graph if |
S
| is even, greater than 2, S is contained in {
a
k
i
b
j
∣
k
i
s
o
d
d
,
0
⩽
j
⩽
2
}, and A
u
t
(
U
6
n
,
S
) acts transitively on S.



---

*Source: 628214-2014-08-19.xml*