# Finite 1-Regular Cayley Graphs of Valency 5

Authors: Jing Jian Li; Ben Gong Lou; Xiao Jun Zhang
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

LetΓ=Cay(G,S) and G≤X≤AutΓ. We say Γ is (X,1)-regular Cayley graph if X acts regularly on its arcs. Γ is said to be core-free if G is core-free in some X≤Aut(Cay(G,S)). In this paper, we prove that if an (X,1)-regular Cayley graph of valency 5 is not normal or binormal, then it is the normal cover of one of two core-free ones up to isomorphism. In particular, there are no core-free 1-regular Cayley graphs of valency 5.


---

## Body

## 1. Introduction

We assume that all graphs in this paper are finite, simple, and undirected.LetΓ be a graph. Denote the vertex set, arc set, and full automorphism group of Γ by VΓ, AΓ, and AutΓ, respectively. A graph Γ is called X-vertex-transitive or X-arc-transitive if X acts transitively on VΓ or AΓ, where X≤AutΓ. Γ is simply called vertex-transitive, arc-transitive for the case where X=AutΓ. In particular, Γ is called (X,1)-regular if X≤AutΓ acts regularly on its arcs and then 1-regular when X=AutΓ.LetG be a finite group with identity element 1. For a subset S of G with 1∉S=S-1:={x-1∣x∈S}, the Cayley graph Cay(G,S) of G (with respect to S) is defined as the graph with vertex set G such that x,y∈G are adjacent if and only if yx-1∈S. It is easy to see that a Cayley graph Cay(G,S) has valency |S|, and it is connected if and only if 〈S〉=G.Li proved in [1] that there are only finite number of core-free s-transitive Cayley graphs of valency k for s∈{2,3,4,5,7} and k≥3 and that, with the exceptions s=2 and (s,k)=(3,7), every s-transitive Cayley graph is a normal cover of a core-free one. It was proved in [2] that there are 15 core-free s-transitive cubic Cayley graphs up to isomorphism, and there are no core-free 1-regular cubic Cayley graphs. A natural problem arises. Characterize 1-transitive Cayley graphs, in particular, which graphs are 1-regular? Until now, the result about 1-regular graphs mainly focused constructing examples. For example, Frucht gave the first example of cubic 1-regular graph in [3]. After then, Conder and Praeger constructed two infinite families of cubic 1-regular graphs in [4]. Marušič [5] and Malnič et al. [6] constructed two infinite families of tetravalent 1-regular graphs. Classifying such graphs has aroused great interest. Motivated by above results and problem, we consider 1-regular Cayley graphs of valency 5 in this paper.A graphΓ can be viewed as a Cayley graph of a group G if and only if AutΓ contains a subgroup that is isomorphic to G and acts regularly on the vertex set. For convenience, we denote this regular subgroup still by G. If X≤AutΓ contains a normal subgroup that is regular and isomorphic to G, then Γ is called an X-normal Cayley graph of G; if G is not normal in X but has a subgroup which is normal in X and semiregular on VΓ with exactly two orbits, then Γ is called an X-bi-normal Cayley graph; furthermore if X=AutΓ, Γ is called normal or bi-normal. Some characterization of normal and bi-normal Cayley graphs has given in [1, 2].For a Cayley graphΓ=Cay(G,S), Γ is said to be core-free (with respect to G) if G is core-free in some X≤AutΓ; that is, CoreX(G)=∩x∈XGx=1.The main result of this paper is the following assertion.Theorem 1.
LetΓ=Cay(G,S) be an (X,1)-regular Cayley graph of valency 5, where G≤X≤AutΓ. Let n(G) be the number of nonisomorphic core-free (X,1)-regular Cayley graph of valency 5 with the regular subgroup equal to G. Then either (i)
Γis anX-normal orX-bi-normal Cayley graph or(ii)
Γis a nontrivial normal cover of one line of Table1.In particular, there are no core-free 1-regular Cayley graphs of valency 5.Table 1
Number
X
G
n (G)
1-regular
Remark
1
A
5
A
4
1
No
Icosahedron
2
S
5
S
4
1
NoBy Theorem1, we can get the following remark immediately.Remark 2.
LetΓ=Cay(G,S) be an 1-regular Cayley graph of valency 5. Then Γ is normal or bi-normal.


## 2. Examples

In this section we give some examples of graphs appearing in Theorem1.Example 3.
LetM=〈a〉≅ℤ11 be a cyclic group. Assume that τ∈Aut(M) is of order 10 and X=M:〈τ〉≅ℤ11:ℤ10. Let
(1)G=M:〈τ5〉≅D22.
Suppose that
(2)S=g〈τ2〉={g,gτ2,gτ4,gτ6,gτ8},
where g∈G is an involution such that g≠τ5. Let Γ=Cay(G,S) be the Cayley graph of the dihedral group G with respect to S. Then Γ is a connected (X,1)-regular Cayley graph of valency 5. In particular, Γ is X-normal.Proof.
Let(3)G=〈a〉:〈b〉={1,a,a2,…,a10,b,ab,a2b,…,a10b}≅D22,
where b=τ5.
Notingo(a)=11, we may assume that aτ=a9. Since the involution g∈G is not equal to b, we may let g=aib for some 1≤i<11 such that (9,i)=1. Then gτ2=(aib)τ2=a81ib=a4ib, and so gτ2g-1=a3i∈〈g〈τ2〉〉=〈S〉. Thus the element gτ2g-1 is of order 11 as (3i,11)=1. So 〈S〉=〈g〈τ2〉〉=G; that is, Γ=Cay(G,S) is connected.
Obviously,G⊲X≤AutΓ and X1=〈τ2〉. However, |X|=55=|AΓ|; then Γ is an (X,1)-regular normal Cayley graph of G of valency 5.Example 4.
LetG=〈a,b∣a5=b2=1,ab=a-1〉≅D10. Set S={b,ab,a2b,a3b,a4b} and Γ=Cay(G,S). Then Γ≅K5,5 and AutΓ=S5≀S2. Let X=(ℤ5×ℤ5):ℤ2≇D10×ℤ5 such that G≤X≤AutΓ. It follows that CoreX(G)≅ℤ5. Then Xα≅ℤ5 for α∈VΓ, and furthermore Γ is (X,1)-regular. Obviously G is not normal in X. However, CoreX(G)⊴X is semiregular and has exactly two orbits on VΓ; then Γ is an (X,1)-regular Cayley graph of valency 5. In particular, Γ is X-bi-normal.


## 3. The Proof of Main Results

In this section, we will prove our main results. We first present some properties about normal Cayley graphs.For a Cayley graphΓ=Cay(G,S), we have a subgroup of Aut(G):
(4)Aut(G,S)={σ∈Aut(G)∣Sσ=S}.Clearly it is a subgroup of the stabilizer inAutΓ of the vertex corresponding to the identity 1 of G. Since Γ is connected, Aut(G,S) acts faithfully on S. By Godsil [7, Lemma 2.1], the normalizer NAutΓ(G)=G:Aut(G,S). So Γ=Cay(G,S) is a normal Cayley graph if and only if Aut(G,S)=(AutΓ)1.LetΓ=Cay(G,S) be an (X,1)-regular Cayley graph of valency 5 such that G≤X≤AutΓ. Then S contains at least one involution. Let K=CoreX(G), which is the core of G in X.Lemma 5.
Assume thatK=1. Then (X,G)=(A5,A4) or (S5,S4).Proof.
LetH be the stabilizer in X of the vertex corresponding to the identity of G. Then H≅ℤ5, H∩G=1, and X=GH. Let [X:G] be the set of right cosets of G in X. Consider the action of X on [X:G] by the right multiplication. Then we get that X is a primitive permutation group of degree 5 and G is a stabilizer of X. Since Γ has valency 5, |G|=|VΓ|≥6, and so |X|=|G||H|≥30. Then we can show X≅A5 or S5, and then G=A4 or S4, respectively.Lemma 6.
Suppose thatG=A4 and X=A5. Then Γ is the icosahedron graph. Moreover, AutΓ=A5×ℤ2 and Γ is not 1-regular.Proof.
Note thatX=GH, where X≅A5, G≅A4, and H≅ℤ5. Since X has no nontrivial normal subgroup, Γ is not bipartite. So Γ is the icosahedron graph. Further by Magma [8], AutΓ=A5×ℤ2, so Γ is not 1-regular.Lemma 7.
Suppose thatG=S4 and X=S5. Then the graph Γ is not 1-regular and there is only one isomorphism class of these graphs.Proof.
Note thatG=S4, X=S5, and X=GH. Let H=〈σ〉, where σ=(12345). By considering the right multiplication action of X on the right cosets of G in X, G can be viewed as a stabilizer of X acting on {1,2,3,4,5}. Without lost generality, we may assume that 1 is fixed by G. Take an involution τ∈S. Then, by [2], τ∈S5∖NS5(H) and we can identify S with HτH∩G. Note that τ∈G≤S4 and NS5(H)=H:Aut(H)=〈(12345)〉:〈(2354)〉≅ℤ5:ℤ4; then τ is one of the following: (25), (35), (23), (34), (45), (24), (23)(45), and (24)(35). Note H=〈(12345)〉. Assume that τ=(25); by calculation, we have (25):=h1, τ·(12345)=(12)(345):=h2, τ·(13524)=(1354):=h3, τ·(14253)=(1423):=h4, and τ·(15432)=(15)(243):=h5. Then H(25)H={Hh1,Hh2,Hh3,Hh4,Hh5}={(25),(15)(234), (1453),(12)(354),(1324),(15)(243),(1423),(1354),(12)(345),(2534), (1524),(145)(23),(13),(1352),(125)(34),(24),(154)(23),(123)(45), (35),(152)(34),(1425),(14),(132)(45),(1253),(2435)}. Thus the corresponding S is {(25),(2534),(24),(35),(2435)} since 1s=1 for each s∈H(25)H. By similar argument, for every τ, we can work out S explicitly, which is one of the following four cases: S1={(25),(2534),(24),(35),(2435)}, S2={(23),(34),(45),(2345),(2543)}, S3={(23)(45),(235),(253),(245),(254)}, and S4={(24)(35),(243),(354),(234),(345)}.
Now letA=AutΓ. We declare that X≠A. Assume that X=A. Note that G=NA(G)=GAut(G,S); then Aut(G,S)=1. Let σ=(25)(34). Since σ=(2534)(25)·(35)=(34)(23)·(2345)=(23)(45)·(253)·(254)=(24)(35)·(243)·(354), σ∈G and Sσ=S for any possible S. Therefore σ∈Aut(G,S), which leads to a contradiction. So the assertion is right; that is, Γ is not 1-regular.
LetGi=〈Si〉 and Γi=Cay(Gi,Si) for i∈{1,2,3,4}. Set γ=(2453), then S1γ=S2 and S3γ=S4. It follows that G1γ=G2 and G3γ=G4, namely, Γ1≅Γ2 and Γ3≅Γ4. Now we consider G1=〈S1〉. Note that (24)=(25)(2435) and (35)=(2534)(25)·(2534)2, then G1=〈(25),(2534)〉. Since (254)=(23)(45)·(235), G3=〈S3〉=〈(23)(45),(235)〉. On the other hand, (2534)4=(25)2=((25)·(2534))3=1 and (235)3=((23)(45))2=((23)(45)·(235))3=1, then G1≅S4 and G3≅A4. By the assumption, Γ3 is not the graph satisfying conditions. So far we get the result that there is only one isomorphism class of graphs when G=S4.To finish our proof, we need to introduce some definitions and properties. Assume thatΓ is an X-vertex transitive graph with X being a subgroup of AutΓ. Let N be a normal subgroup of X. Denote the set of N-orbits in VΓ by VN. The normal quotient ΓN of Γ induced by N is defined as the graph with vertex set VN, and two vertices B, C∈VN are adjacent if there exist u∈B and v∈C such that they are adjacent in Γ. It is easy to show that X/N acts transitively on the vertex set of ΓN. Assume further that Γ is X-edge-transitive. Then X/N acts transitively on the edge set of ΓN, and the valency val(Γ)=mval(ΓN) for some positive integer m. If m=1, then Γ is called a normal cover of ΓN.Proof of Theorem1.
LetΓ=Cay(G,S) be an (X,1)-regular Cayley graph of valency 5, where G≤X≤AutΓ. Then it is trivial to see that Γ is connected. Let N=CoreX(G) be the core of G in X. Assume that N is not trivial. Then either G=N or |G:N|≥2. The former implies G⊴X; that is, Γ is an X-normal Cayley graph with respect to G. For the case where |G:N|=2, it is easy to verify Γ is an X-bi-normal Cayley graph. Suppose that |G:N|>2; namely, N has at least three orbits on VΓ. Since val(Γ)=5 is a prime and Γ is (X,1)-regular, Γ is a cover of ΓN and G/N≤X/N≤AutΓN. We have that ΓN is a Cayley graph of G/N and ΓN is core-free with respect to G/N. Now suppose that N is trivial, then Γ is a core-free one. According to Lemmas 5, 6, and 7, there are two core-free (X,1)-regular Cayley graphs of valency 5 (up to isomorphism) as in Table 1. As far, Theorem 1 holds.



---

*Source: 125916-2013-03-27.xml*