Classifying a family of edge-transitive metacirculant graphs

DOI 10.1007/s10801-011-0311-7

Classifying a family of edge-transitive metacirculant graphs

Shu-Jiao Song·Cai Heng Li·Dianjun Wang

Received: 21 July 2010 / Accepted: 23 August 2011 / Published online: 14 September 2011

© Springer Science+Business Media, LLC 2011

Abstract A characterization is given of the class of edge-transitive Cayley graphs of Frobenius groupsZp^d:Zq withp, qodd prime, of valency coprime top. This char- acterization is then used to study an isomorphism problem regarding Cayley graphs, and to construct new families of half-arc-transitive graphs.

Keywords Edge-transitive·Metacirculant·Half-arc-transitive·Cayley graph

1 Introduction

A graphΓ =(V , E)is calledX-edge-transitive ifX≤^AutΓ is transitive on the edge setE. A graphΓ =(V , E)is a Cayley graph if there exists a groupGand a subset S⊂GwithS=S⁻¹= {s⁻¹|s∈S}such that the vertex setV can be identified with Gandx is adjacent toyif and only ifyx⁻¹∈S. A circulant is a Cayley graph of a cyclic group. Edge-transitive circulants have been characterized by Kovács [6] and Li

This work forms a part of the first author’s PhD project and it is supported by the National Natural Science Foundation of China.

S.-J. Song (

Department of Mathematical Sciences, Qinghua (Tsing Hua) University, Beijing 100084, P. R. China e-mail:[email protected]

D. Wang

e-mail:[email protected] C.H. Li

School of Mathematics and Statistics, Yunnan University, Kunming, Yunnan 650091, P. R. China C.H. Li

Centre for the Mathematics of Symmetry and Computation, School of Mathematics and Statistics, The University of Western Australia, Crawley 6009, WA, Australia

e-mail:[email protected]

[12] independently. It would be a natural next step toward a characterization of edge- transitive metacirculants (which admit a vertex transitive metacyclic group), see [7]

for the study of arc-regular dihedrants. In this paper, we characterize a special class of metacirculants.

A groupX with PSL(d, q)≤X≤PL(d, q) naturally acts on the set Ω of 1- subspaces of the vector spaceF^d_q. Then a pointω∈Ω is a 1-dimensional subspace, and a point stabilizer ofX has the form[q^d−1]._(d,q¹₋₁₎GL(d−1, q).o, where o= X/PSL(d, q), called a parabolic subgroup and denoted byP₁.

Theorem 1.1 LetG=Z_p^d:Zq be a Frobenius group, withp, q odd primes. LetΓ be anX-edge-transitive Cayley graph ofGof valency coprime top, whereG < X≤ AutΓ. Then one of the following statements holds:

(i) Xis almost simple and quasiprimitive onV, and eitherΓ =K_pdqord=1;

(ii) Γ =Cq[K_pd] −p^dCq, andX=PGL(q, r^q).q, andXα=P1∩PGL(q, r^q), or Γ =K_pd×Cq, andXis as in Lemma2.7(iii);

(iii) Gis normal inX;

(iv) Xhas a normal subgroup which is cyclic and regular on the vertex set, and the valency ofΓ is divisible byq;

(v) Γ =Σ[Kq], andXhas a minimal normal subgroup which is not simple, where Σis an edge-transitive circulant of orderp^dand of valency divisible byq.

Remarks on Theorem 1.1

(1) Edge-transitive graphs of orderpqare characterized in [17], and thus the graphs in (i) are known.

(2) A graph is called a normal Cayley graph ifAutΓ contains a normal regular sub- group. In particular, if the normal regular subgroup is cyclic, thenΓ is called normal circulant. For normal Cayley graphΓ ,AutΓ is determined byAut(G), see Lemma 4.1. Thus in part (iii)–(iv), the groupXis well-characterized.

A graphΓ =(V , E)is called half-arc-transitive ifAutΓ is transitive onV andE but intransitive on the arcs (recall that an arc is an ordered pair of adjacent vertices).

In the literature of algebraic graph theory, studying half-arc-transitive graphs is a hot topic, see [2,14,15,18] for references. The characterization given in Theorem1.1 enables us to construct half-arc-transitive graphs.

Theorem 1.2 LetG=Zp^d:Zq be a Frobenius group, where p, q are odd primes.

Then for each integerksuch thatk >1, 2k|(p−1)and(k, q)=1, there are exactly

q−1

2 non-isomorphic connected edge-transitive Cayley graphs of Gof valency 2k, which are all half-arc-transitive.

Next we apply Theorem1.1to study an isomorphism problem of Cayley graphs, that is, Problem 6.3 of the survey [10]. This was one of the main motivations for this work. The isomorphism problem for graphs is fundamental and difficult. One way to study the isomorphism problem for Cayley graphs is to determine whether the isomorphism between two Cayley graphs is determined by an automorphism of the defining group.

Table 1 AutΓ with an

insoluble subgroup X G Xα val(Γ ) AutΓ

PSL(2, p) p:^p−₂¹ D_p+1 ^p+₂¹ PGL(2, p) p+1

4 X

PGL(2, p) p:^p−₂¹ D_2(p+1) ^p+₂¹ X

PSL(2,11) 11:5 A₄ 4, 6 PGL(2,11)

PGL(2,11) 11:5 S₄ 4, 6, 8 X

PSL(2,23) 23:11 S₄ 4, 6, 8, 12 X

PSL(2,29) 29:7 A₅ 12 X

PSL(2,59) 59:29 A₅ 6, 10, 12, 20, 24, 30 X

A Cayley graphCay(G, S)is called a CI-graph of G if, for any Cayley graph Cay(G, T ), whenever ^Cay(G, S)∼=^Cay(G, T ) we have S^σ =T for some σ ∈ Aut(G). (CI stands for a Cayley isomorphism.)

LetGbe a group and q the smallest prime divisor of|G|. It was shown in [8]

that each connected Cayley graph ofGof valency less thanqis a CI-graph, and then in [9] examples were constructed to show that connected Cayley graphs of valency q are not necessarily CI-graphs. Problem 6.3 in [10] proposed to characterize such Cayley graphs. Theorem1.1enables us to construct another type of example, given in the following theorem.

Theorem 1.3 LetG=Zp^d:Zqbe a Frobenius group, wherep, qare odd primes. Let Γ be a connected undirected Cayley graph ofGof valency at most 2q. Then one of the following occurs:

(i) Gis a Hall normal subgroup ofAutΓ, andΓ is a CI-graph ofG;

(ii) Γ is arc-transitive of valency 2q, and^AutΓ ∼=(Zp^d:Z2q)×Zq; furthermore, if q≥5,Γ is not a CI-graph ofG.

(iii) G=Zp:Zq, and lies in Table1.

Comparing with Theorem1.2, the next result is somehow a bit surprising.

Corollary 1.4 All connected edge-transitive Cayley graphs of valency 2q of the Frobenius groupZp^d:Zqwithp, qodd primes are isomorphic and arc-transitive cir- culants.

2 Transitive permutation groups of degreep^dq

LetX be a transitive permutation group onΩ. If Ω has a non-trivial X-invariant partitionBsay, thenXis called imprimitive, andXinduces a transitive permutation group onB, denoted byX^B. On the other hand, ifΩ has no non-trivialX-invariant partition thenXis said to be primitive. AnX-invariant partitionBis called minimal if for a blockB∈B, the induced actionX^B_Bis primitive.

Lemma 2.1 LetX≤Sym(Ω)be transitive. LetBbe a minimalX-invariant partition ofΩ, and letK be the kernel ofXacting onB. Assume that^soc(X_B^B)is simple for B∈B, andK=1. Then the following statements hold:

(i) Kacts onBfaithfully if and only ifsoc(K)is simple.

(ii) soc(K)is a characteristically simple group.

(iii) In the case wheresoc(K)is not simple, for eachC∈B, the action ofK_(B)onC is trivial or transitive, and there exists at least oneCon whichK_(B)is transitive.

Proof Since B is a minimal X-invariant partition of Ω, the induced permutation groupX^B_B is primitive. Let N=^soc(K). ThenN=1, and it follows thatN^B=1, that is,N^B is a non-trivial normal subgroup ofX_B^B. Sincesoc(X_B^B)is simple, so is N^B.

Suppose thatN=^soc(K)is simple. SinceNis normal inX, the actions ofN on all blocks inBare equivalent. Thus, ifNacts trivially onB, thenNis trivial on every block inB, which is not possible. SoN is non-trivial onB, and it follows thatKis faithful onB. Suppose on the other hand thatN is not simple. SinceN^B is simple, we haveK_(B)≥N_(B)=1, as in part (i).

LetSbe a simple direct factor ofN. ThenSNX, andSacts non-trivially on some blockC∈B. Thus,S∼=S^CN^CX^C_C. Sincesoc(X^C_C)∼=^soc(X^B_B)is simple, it follows thatSis isomorphic tosoc(X^C_C). HenceN=^soc(K)is a direct product of isomorphic simple groups, that is,N is characteristically simple, as in part (ii).

Suppose that for a blockC∈B, the actionN_(B)onCis non-trivial. ThenN_(B)^C N^C X_C^C. Since ^soc(X_C^C)is simple, it follows that N_(B)^C ≥^soc(X^C_C)andN_(B)^C is transitive, and so isK_(B)^C .

SinceN_(B)=1, there exists at least one blockB ∈Bon whichN_(B) acts non-

trivially, as in part (iii).

IfNX, a normal subgroup ofX, then eitherN is transitive onΩ, or the set of N-orbits onΩis anX-invariant partition ofΩ, called a normal partition. It follows that any non-identity normal subgroup of a primitive permutation group is transitive.

For any permutation groupX, if each non-trivial normal subgroup ofXis transitive thenXis called quasiprimitive. Hence primitive groups are quasiprimitive; however, the converse statement is not true.

Next we assume thatXcontains a metacyclic regular subgroup G= a:b ∼=Zp^d:Zq,

wherep, q are odd primes. Then|Ω| =p^dq. Assume further thatGis a Frobenius group, equivalently in this case, the center Z(G)=1.

The primitive case is known by a recent publication [13]. The following lemma gives a list of triples(X, G, Xω)whereω∈Ω, which is read out of Tables 16.1–16.3 of [13].

Lemma 2.2 IfXis primitive onΩ, then eitherG≤X≤AGL(1, p)or(X, G, X_ω) is one of the triples in Table2.

Table 2 Primitive groupX

with subgroupG X G Xω condition

PGL(q, r) _(r^rq₋⁻¹_1)q:q P₁ rprime,q(r−1)

PGL(2,11) 11:5 S₄

PGL(2,23) 23:11 S₄

PSL(2,29) 29:7 A₅

PSL(2,59) 59:29 A₅

PSL(5,2) 31:5 P2

M₁₁ 11:5 M₉.2

M23 23:11 M21.2

23:11 2⁴:A₇

Ap p:^p−1₂ S_p−2 q=^p−1₂

Table 3 Primitive groupXof

orderp^d P Pω p^d Condition

A_pd,S_pd A_pd−1,S_pd−1

PGL(n, r) P1 rⁿ−1

r−1 n, rprime PGL(n, rⁿ),PGL(n, rⁿ).n P1 rⁿ²−1

rⁿ−1 n, rprime

PSL(2,11) A₅ 11

M11 M10 11

M₂₃ M₂₂ 23

Next, we assume thatXis imprimitive onΩ. The following result is a special case in [5] and [11], which will be frequently used.

Lemma 2.3 LetP be a quasiprimitive permutation group onΩthat contains a reg- ular subgroupZ_p^d withpprime. ThenP is primitive onΩ, and further, eitherd=1 andP ≤AGL(1, p), orP is almost simple and 2-transitive, listed in Table3.

LetBbe a non-trivial X-invariant partition ofΩ, and letK be the kernel ofX acting onB.

Lemma 2.4 Using the above notation, either (i) |B| =p^dandais regular onB, or

(ii) 1=K∩G≤ a, andG^B ora^Bis regular.

Proof SinceKX, we haveK∩GG. SinceGis transitive onΩ, the factor group G/(K∩G)is a transitive Frobenius group onB. IfK∩G=1, then sinceK∩Gis a proper normal subgroup ofGandGis a Frobenius group, we haveK∩G≤ a. SinceG^B∼=G/(K∩G)is transitive, it follows thatG^B_B=1 orZq, and hencea^B orG^Bis regular, respectively.

Suppose thatK∩G=1. ThenGis faithful onB, andG∼=G^B. Thus, the point stabilizerG^B_BofGacting onBis core free. Since the only core free subgroups ofG

Table 4 Quasiprimitive and not primitive groupX

X G Xω Comments

PGL(q, r) ^r_r−^q−1₁:q [q^q−1]:_q¹GL(q−1, r)

PGL(q, r^q) ^rq

2−1

r^q−1:q [q^q−1]:q¹GL(q−1, r^q) rprime,q(r−1) PGL(q, r^q).q ^rq

2−1

r^q−1:q [q^q−1]:q¹GL(q−1, r^q).q

PSL(2,11) 11:5 A₄

are isomorphic toZq, we conclude thatG_B∼=Zq, and thusa ∼=Z_p^d acts regularly

onB.

The following lemma determines the quasiprimitive case.

Lemma 2.5 IfXis quasiprimitive and imprimitive onΩ, then(X, G, Xω)is one of the triples in Table4.

Proof LetBbe a non-trivialX-invariant partition of Ω. SinceX is quasiprimitive onΩ, X∼=X^B is faithful, and by Lemma 2.4, we have |B| =p^d and X^B has a cyclic regular subgroup. By Lemma2.3,X∼=X^B lies in Table3, andG≤NX(a).

Furthermore, forB∈B, we haveXB=GBXω withGB=Zq. It then follows that

(X, G, X_ω)lies in Table4.

We next consider minimal block systems. Assume thatBis a minimalX-invariant partition of Ω. Take a block B∈B. Then the induced permutation group X^B_B is primitive.

Lemma 2.6 Assume thatK=1 andK∩G=1. Then|B| =q, and eithersoc(K) is non-simple and acts onB unfaithfully, orK=Zqanda ×K∼=Zp^dqis regular onΩ.

Proof By Lemma2.4,|B| =q, andais regular onB. HenceZq∼= b ≤GB, and soc(X^B_B)is simple. Ifsoc(K)is not simple, then by Lemma2.1,soc(K)is unfaithful onB.

Assume thatsoc(K) is simple. Then by Lemma2.1,K∼=K^B. By Lemma2.3, eitherK∼=K^BX_B^B≤AGL(1, q), or K is almost simple. It follows thatKG= K×G. SinceGis regular onΩ, we conclude thatK∼=Zq, andKis semiregular on

Ω. Soa ×Kis regular onΩ.

Lemma 2.7 Assume thatK∩G=1. Thensoc(K)is characteristically simple, and one of the following holds:

(i) soc(K)is not simple and acts onBunfaithfully;

(ii) X=PGL(q, r^q).q, G=Z_rq²₋₁

rq−1

:Zq, andX_ω =P1∩PGL(q, r^q), where r is prime;

Table 5

X G Xω Condition

(A_pd×Zq).o Z_pd:Zq A_pd−1.o q(p−1),o=1 or 2

PGL(q, r)×Zq Zrq−1 r−1 :Zq PGL(q, r^q)×Zq Z_rq2

−1 rq−1

:Zq P₁(parabolic) rprime

PGL(q, r^q).q×Zq Z_rq2

−1 rq−1

:Zq

PSL(2,11)×Z5 11:5 A₅

M₁₁×Z5 11:5 A₅

M23×Z11 23:11 M22

(iii) (X, G, X_ω)is a triple of Table5;

(iv) G=Zp:Zq, andX=Zp:Zqk≤AGL(1, p);

(v) K∼=Zp.

Proof The primitive permutation groupX^B_B contains a regular subgroupG^B_B, which is cyclic or Frobenius. By Lemmas2.2and2.3, the socle ofX^B_B is simple. Since K=1, by Lemma2.1,^soc(K)is characteristically simple; furthermore, if^soc(K)is not simple, thensoc(K)acts onBunfaithfully, as in part (i).

Assume next thatsoc(K)is simple. By Lemma2.1, we haveK_(B)=1, andK∼= K^BX^B_B. Then by Lemmas2.2and2.3, eitherK=Zp:Zl withl(p−1), orK∼= K^Bis almost simple and lies in Table2or3.

IfK=Zp, then part (v) is satisfied. Assume thatK=Zp:Zl≤AGL(1, p)with l=1. ThenK∩G=Zp,K=(K∩G):K_ω, withK_ω∼=Zl, andK∩GXsince K∩Gis a characteristic subgroup ofK. Suppose thatd >1. Thena ≤CX(K∩ G)X, and so(Ka)/(K∩G)∼= a ×Kω, wherea = a/K∩G. It follows thatK_ωcentralizesa, and henceK_ωcharKX, which is not possible. Sod=1, and G=Zp:ZqandX=Zp:Zqk≤AGL(1, p), as in part (iv).

Thus, we may assume thatKis almost simple.

Case 1. Suppose CX(K)=1.

ThenX≤^Aut(K), and X is almost simple of which the socle equalssoc(K).

SinceK∼=K^BX_B^B, the primitive groupX_B^Bis almost simple and lies in Table2or Table3, and so isK^B(∼=K). SinceK∩Gis normal inG, it follows thatKlies in Table3. AsKis the kernel of a minimal invariant partition ofΩ,Kis intransitive on Ω, and thusK∩Gis a proper subgroup ofG. Now|B| = |K:K_α|,|Ω| = |X:X_α|, and|B|divides|Ω|. Noticing that|K:K_α| = |B|divides|X:X_α| = |Ω|, we have

|B| = ^|_|K^X:_:^X_K^α_α^|_| = ^|_|^X_K^|_|· ^|_|^K_X^α_α|^|.Furthermore, as |Ω| =p^dq and(pq,|Xα|)=1,p or q divides^|_|^X_K^|_|= |X/K|. Sincep, qare odd primes, by Table2and Table3, we conclude thatsoc(K)=PSL(n, r)or PSL(n, rⁿ), wheren, r are primes. For the former,X≤ K.Out(K)=PSL(n, r).(n, r−1), or PSL(n, r).(n, r−1).2. Thus X=PSL(n, r), PSL(n, r).2, PSL(n, r).n, or PSL(n, r).n.2 withp^d=^r_rⁿ₋⁻₁¹.SinceZp^d:Zq∼=G≤X, we haven=q. Similarly, for the latter case for which soc(K)=PSL(n, rⁿ), we

haven=q. On the other hand,X^B_B lies in Table 2or Table3, andX_B^B≤X. Thus X=PGL(q, r^q).qsatisfying part (ii).

Case 2. LetC:=CX(K)=1.

ThenX=(KC).H=(K×C).H, whereH≤^Out(K). IfC∩G=1, then(K∩ G)×(C∩G)is a normal subgroup ofG, which is not possible. Thus,C∩G=1, and by Lemma2.4, an orbit ofConV is of lengthq. LetCbe the set ofC-orbits on V, and letLbe the kernel ofXacting onC. By Lemmas2.4,2.2and2.3, eitherLis almost simple which contains a regular cyclic groupZq, and has the form in Table3, or L≤AGL(1, q). Since G=Zp^d:Zq, the intersection L∩G=1. Moreover, as LLG, we haveLG=L:G. In both cases, there is no automorphism ofLof order qorp. ThusLG=L×G, that is,GcentralizesL, and sinceGis regular onV, we conclude thatL=C=Zq. Thus,X=(K×Zq).H, andX^C∼=X/L∼=K.H. Now

|C| =p^d, andX^Cis a permutation group onCand contains a cyclic regular subgroup.

SinceKis almost simple, so isX^C. By [11, Corollary 1.4],X^Cacts onCprimitively, and thusX^Csatisfies Lemma2.3. NowXis an extension ofZqbyX^C. Noticing that Zp^d ≤G≤X^C, it is easily shown thatXsatisfies part (iii).

3 Proof of Theorem1.1

We prove Theorem1.1in this section. We first study some examples appearing in the theorem.

For graphsΔ=(U, E)andΣ=(W, F )with vertex setsU andW, respectively, we define lexicographic productΔ[Σ]and direct productΔ×Σ, both with vertex set V =U×W= {(u, w)|u∈U, w∈W}. The adjacency is defined as follows: given two verticesv1=(u1, w1)andv2=(u2, w2)inV,

(a) forΔ[Σ], two vertices(u₁, w₁)and(u₂, w₂)are adjacent if and only if either u1, u2are adjacent inΔoru1=u2andw1, w2are adjacent inΣ;

(b) for Γ ×Σ, two vertices (u1, w1) and (u2, w2) are adjacent if and only if {u₁, u₂} ∈Eand{w₁, w₂} ∈F.

Example 3.1 Let X =PGL(q, r^q).q where q is an odd prime, let X_ω =P₁∩ PGL(q, r^q)= [r^q(q−1)]:GL(q−1, r^q), and let Ω = [X:Xω]. Then|Ω| = ^r_r^qq²−⁻1¹, andXhas a subgroupG=Z_rq²₋₁

rq−1

:Zq which is regular onΩ. Assume that^rq

2−1

r^q−1 =p^dfor some primep. LetK=PGL(q, r^q)X. SinceXω<

K, the normal subgroupKis intransitive and has exactlyqorbits onΩ. LetBbe the set ofK-orbits onΩ, and letB= {B₁, B₂, . . . , B_q}. Then|B| =q, and|B| =^r_r^qq²−⁻1¹. LetΓ be a connected orbital graph. Then the quotient graph Γ_K is a circulant of orderq.

Sinceq≥3, the linear groupK has exactly two inequivalent 2-transitive permu- tation representations of degree ^rq

2−1

r^q−1. Suppose thatK^Bi andK^Bj are not equivalent for some blocksBi andBj. Then, relabeling if necessary, assume thatK^B1, . . . , K^Bt are equivalent toK^Bi, andK^Bt+1, . . . , K^Bq are equivalent toK^Bj. Thus, the quotient Γ_Kis bipartite, which is not possible. So the actions ofKonB_i are all equivalent.

LetB₁andB_jbe such that the induced subgraph[B₁∪B_j]has at least one edge.

Letα∈B₁andβ∈B_j be such thatK_α=K_β. Suppose thatαis adjacent toβ. Since Γ isX-edge-transitive andKα=Xα, it follows thatKα fixesΓ (α)pointwise. Since Γ is connected, it follows thatKα fixes all vertices ofΓ, and thusKis semiregular onΩ, which is a contradiction. Thusαis not adjacent toβ. SinceKis 2-transitive onB_j, the stabilizerK_α =K_β is transitive onB_j \ {β}. It follows that[B₁, B_j] = K_pd,p^d −p^dK2. On the other hand, sinceK_α =X_α andΓ isX-edge-transitive, we conclude thatΓK=Cq, andΓ =Cq[K_pd] −p^dCq.

Example 3.2 LetΓ =K_pd ×Cq, whereq dividesp−1. ThenAutΓ =S_pd×D2q. LetP ≤S_pd be a 2-transitive group which contains a regular subgroup R∼=Zp^d

such that NP(R)contains a Frobenius groupR:zwherez ∼=Zq. LetX=P×C, whereC= c =Zq. ThenΓ isX-edge-transitive, and the subgroupR:zc< Xis a Frobenius group and regular onV Γ.

To prove Theorem1.1, we refine a result for edge-transitive circulants.

Lemma 3.3 LetΓ =(V , E)be a connectedX-edge-transitive circulant of orderp^d withp prime such that X contains a regular cyclic subgroupG. Assume that the valency of Γ is coprime top. Then eitherΓ =K_pd and X is almost simple and 2-transitive, orGis normal inX.

Proof IfXis primitive onV, then eitherXis almost simple and 2-transitive, soΓ is a complete graph, orX≤AGL(1, p). Then the lemma holds.

Thus, we next assume thatXis imprimitive. Suppose thatXhas two minimal nor- mal subgroupsM, N. LetBandCbe the sets ofM-orbits andN-orbits, respectively, onV. LetK, Lbe the kernels ofXacting onB,C, respectively. By [11, Lemma 3.1], we haveK∩G=1, andL∩G=1. Hence(K∩G)×(L∩G)≤G∼=Zp^d, which is not possible. Thus,Xhas a unique minimal normal subgroup, sayM.

LetBbe a minimalX-invariant partition ofV, and letB∈B. LetKbe the kernel of X acting on B, and let X=X/K. Then X^B_B is primitive, and by Lemma2.3, soc(X^B_B)is simple.

Suppose thatsoc(K) is not simple. By Lemma2.1,soc(K)is characteristically simple and acts non-trivial onB, and there existsB ∈Bon whichK_(B)is transitive.

It follows that the induced subgraph[B, B] =Kp^c,p^c, wherep^c= |B|. Thus,Γ = Γ_B[Kp^c], which is not possible since the valency ofΓ should be coprime top.

Hencesoc(K)is simple. ThenK∼=K^BX_B^B. Hence eitherKis almost simple or K=Zp:Zl≤AGL(1, p). LetC=CX(K). ThenX=(CK).H, whereH≤^Out(K).

IfC=1, then eitherX is almost simple, orX=Zp:Zl≤AGL(1, p), andH has order coprime top. SoXis primitive, which is a contradiction. HenceC=1.

Suppose thatK is not abelian. ThenCK=C×K, and henceXhas a minimal normal subgroup that is contained inC, which contradicts the previous conclusion thatXhas only one minimal normal subgroup. Thus,K∼=Zp.

By the inductive assumption,Γ_BandX satisfy the lemma. Suppose thatXis al- most simple. By Lemma2.3,Xlies in Table3. It follows thatK×^soc(X)K.X,

andGhas two minimal normal subgroups. This is not possible sinceXhas no sub- group which is isomorphic toZ²_p. Thus,G/K is normal inX=X/K, and soGis

normal inX, as claimed.

The following conclusion is a consequence of Lemma3.3.

Lemma 3.4 LetΓ =(V , E)be a connected circulant of orderp^d and valency at mostp−1, withpodd prime. Assume thatZ_p^d ∼=G≤^AutΓ andGis regular onV. Then eitherΓ =Kp, orGis normal inAutΓ.

Proof LetR= a ∼=Z_p^d be such that Γ =^Cay(R, S), and let X=^AutΓ. Then S =R, and soScontains an element of orderp^d. Without loss of generality, assume a∈S. LetΣ be the graph with vertex setV and edge set {1, a}^X. Then Σ is a connectedX-edge-transitive Cayley graph ofR, andX≤^AutΣ.

IfΣ=K_pd, then since the valency ofΣis at mostp−1, we conclude thatd=1 andΓ =Σ=Kp. Assume thatΣ is not a complete graph. By Lemma3.3,G is

normal inX.

Now we are ready to prove Theorem1.1.

Proof of Theorem1.1 LetG,Γ andXbe as in the theorem. IfXis primitive onV, then by Lemma 2.2, eitherG≤X≤AGL(1, p)or(X, G, Xα), whereαis a vertex, lies in Table2and part (i) of Theorem 1.1is satisfied.

Thus, we assume thatX is imprimitive onV. Let B be a minimalX-invariant partition ofΩ, and letB∈B. LetK be the kernel ofX acting onB. Ifsoc(K)is not simple, then by Lemma2.1,K_(B)=1. It follows thatK_(B)is transitive onCfor some blockC∈Bwhich is adjacent toB. Thus, the induced subgraph[B, C] ∼=Kl,l, wherel= |B|. Since the valency ofΓ is not divisible byp, we have(l, p)=1. Hence l=q, and soΓ =Σ[Kq], as in part (v).

IfK=1, then X∼=X^B andΓ_B is an edge-transitive circulant of orderp^d. By Lemma3.3, eitherΓ_B=K_pd andX^B is almost simple 2-transitive, orG∼=G^B X^B∼=X. For the former,Xitself is almost simple and quasiprimitive, as in part (i).

Thus, we next assume thatK=1 andsoc(K)is simple. ThenK∼=K^Bis faithful.

Assume now thatK∩G=1. By Lemma2.6, we haveK=Zq. Hence,Gcen- tralizesK, and soa ×K∼=Zp^dqis regular onV. Further,ais normal inX/K, anda ×Kis normal inX. Henceq divides the valency ofΓ as in part (iv).

Assume thatK∩G=1. Then one of parts (ii)–(iv) of Lemma2.7is satisfied.

First consider the triple (X, G, X_α) in part (ii) of Lemma 2.7. Then X = PGL(q, r^q).q, p^d = ^r_r^qq²−⁻1¹, and K =PGL(q, r^q). For two adjacent orbits B, B of K, the actions of K on B and B are equivalent and 2-transitive. It follows that the induced subgraph [B, B] ∼=Kl,l−lK2 with l = |B| =p^d, and hence Γ ∼=Cq[Kp^d] −p^dCq.

Now consider part (iii) of Lemma2.7. It is shown that Γ =K_pd ×Cq, as in Example3.2.

For part (iv) of Lemma2.7, we haveX≤AGL(1, p), andGis normal inX.

Finally, for part (v) of Lemma2.7, we have Zp=K <a. IfV has another minimalX-invariant partitionCwithL being the kernel ofX onC. ThenL∼=Zp

sinceZ²_p≤X,and hencep^ddivides|C|. Then the previous argument withCin place ofBshows that the theorem holds. Thus to complete the proof of Theorem1.1, we may further assume thatBis the unique minimalX-invariant partition ofV. It follows thatKis the unique minimal normal subgroup ofX. Thus,Xis an extension ofKby X:=X/K∼=X^B≤^AutΓ_K. We assume inductively thatΓ_Ksatisfies the statement of the theorem.

LetC=CX(K). Thena∈CX, andX/C≤^Aut(K)∼=Zp−1. IfXhas a non- abelian minimal normal subgroupN, thenK.N is a non-split extension ofK=Zp

byN. HenceZpis a factor group of the Schur multiplier ofN, which is not possible, refer to [4]. It follows that a is normal in X, and thusa is normal inX. Then eitherGis normal inX, orXhas a cyclic regular subgroup.

4 Normal Cayley graphs

Here we study some properties of Cayley graphs, and give a proof of Theorem1.2.

LetΓ be a Cayley graph of a groupG. Then the right multiplications of elements ofGinduce automorphisms ofΓ, that is,

ˆ

g: x→xg, for allg, x∈G.

Further,G∼= ˆG= { ˆg|g∈G}, andGˆ ≤^AutΓ. For an elementg∈G, the left multiplication:

ˇ

g: x→g⁻¹x, x∈G

is not necessarily an automorphism ofΓ. However, inside Sym(G), there is a relation betweenGˆ andG:ˇ Gˆ centralizesG, namely,ˇ Gˆ ◦ ˇG= ˆG,Gˇ<Sym(G).

We observe that, for an elementg∈G, ˇ

ggˆ: x→g⁻¹xg,

which is an inner automorphism ofGinduced byg, denoted byg. Let˜ G˜ = { ˜g|g∈ G}. ThenG˜ =^Inn(G).

For a subgroupHof a groupX, denote by NX(H )and CX(H )the normalizer and the centralizer ofHinX, respectively. It is easily shown that CSym(G)(G)ˆ = ˇG, and GCˆ Sym(G)(G)ˆ = ˆGGˇ = ˆG: ˜G= ˆG:^Inn(G). Moreover, for Cayley graphs, we have the following statements, refer to [3].

Lemma 4.1 For a Cayley graphΓ =^Cay(G, S), we have the following property:

NAutΓ(G)ˆ = ˆG:^Aut(G, S), and GCˆ AutΓ(G)ˆ = ˆG:^Inn(G, S).

To prove Theorem1.2, we need to find Aut(G) for the Frobenius group G= Zp^d:Zq.

Lemma 4.2 LetG= a:b ∼=Zp^d:Zqbe a Frobenius group withp, qprimes. Then Aut(G)= ρ, τ ∼=Z_p^d:Z_p^d−1(p−1), where

ρ:a→a^s, b→b, where(s, p)=1, τ :a→a, b→ab.

In particular, an element ofGof orderqis not conjugate to its inverse under^Aut(G), and elements ofAut(G)of orderq are inner automorphisms ofG.

Proof By definition, we haveb⁻¹ab=a^r, wherer^q≡1(modp^d). Letσ∈^Aut(G).

Sinceais a characteristic subgroup ofG,σ mapsa toa^x, where(x, p^d)=1, and σ mapsbtoa^yb^mfor some integersy, m, withm=0. We claimm=1, that is,σ mapsbtoa^yb.

Now(ab)^σ=a^σb^σ =a^xa^yb^m=a^ya^xb^m. Sinceab=ba^r, we also have(ab)^σ= (ba^r)^σ =a^yb^ma^rx. Thus, a^ya^xb^m =a^yb^ma^rx, and hence a^xb^m =b^ma^rx, and b^−ma^xb^m=a^rx. Becauseb⁻¹ab=a^r, we obtainb^−ma^xb^m=a^xrm. Thusrx≡xr^m (modp^d), which implies thatr^m−1≡1(modp^d). Hencem−1≡0(modp^d)and σ mapsbtoa^yb.

We claim thatσ is uniquely determined by the parametersxandy. Let σ1: a→a^x1, b→a^y1b,

σ2: a→a^x2, b→a^y2b.

Ifσ1=σ2, thena^x1 =a^σ1=a^σ2=a^x2 anda^y1b=b^σ1 =b^σ2=a^y2b. Sox1−x2≡ 0(modp^d)andy1−y2≡0(modp^d).Thus,

Aut(G)=

σ|σ:a→a^x, b→a^ybsuch that x, p^d

=1 , and in particular,|^Aut(G)| =p^d.p^d−1(p−1).

Letρ, τ∈^Aut(G)be such that

ρ: a→a^s, b^ρ→b, where(s, p)=1, τ: a→a, b→ab.

Theno(ρ)=p^d−1(p−1), and o(τ )=p^d. Calculation shows that ρ⁻¹τρ=τ^δ. It follows that τ is a normal subgroup of ^Aut(G), and hence ^Aut(G)= τ:ρ ∼=

Zp^d:Zp^d−1(p−1).

The following lemma will be used to determine isomorphism classes of Cayley graphs.

Lemma 4.3 ([8]) LetGbe a finite group, and letΓ =^Cay(G, S). Assume thatGis of odd order, and assume further thatGˆ is a Hall subgroup ofAutΓ. Then for subset S ⊂Gsuch thatΓ ∼=^Cay(G, S), there existsσ∈^Aut(G)such thatS^σ =S.

Now we are ready to prove Theorem1.2.

Proof of Theorem1.2 LetG= a:b ∼=Zp^d:Zqbe a Frobenius group. Suppose that kis a divisor ofp−1 which is bigger than 2 and coprime topq. LetΓ =^Cay(G, S) be connected, undirected, edge-transitive, and of valency 2k. Since(2k, pq)=1 and 2k(p−1), by [16,17], this is not possible. Thus by Theorem1.1Gˆ is normal in AutΓ. Thus, by Lemma4.1, we conclude that

AutΓ = ˆG:^Aut(G, S).

SinceΓ is connected, we haveS =G, and asΓ is undirected,S= {s₁, s₁⁻¹, . . . , s_k, s_k⁻¹}. Further, asΓ is edge-transitive andAutΓ = ˆG:^Aut(G, S), we conclude that the subsets{s_i, s_i⁻¹}with 1≤i≤kare all conjugate in^Aut(G, S). Therefore, since G=Zp^d:Zqis Frobenius, all elements ofSare of orderq. As|S| =2kis coprime to pq, it follows from Lemma4.2thatAut(G, S)= τ ∼=Zk, and soAutΓ = ˆG:τ ∼= G:Zˆ k. In particular, an element of orderqis not conjugate inAutΓ to its inverse, and therefore,Γ is not arc-transitive.

Subgroups ofX of orderq are Sylow q-subgroups, and hence they are conju- gate. Thus, we may assume thats1is conjugate tobⁱ, where 1≤i≤^q−₂¹. ThenSis conjugate to

S_i=

bⁱ, b⁻ⁱτ.

Noticing thatGˆ is a Hall subgroup ofAutΓ, by Lemma4.3,Γ is a CI-graph. It is easily shown that the subsetsSi with 1≤i≤ ^q−₂¹ are pairwise non-conjugate un- derAut(G). SoCay(G, S_i)with 1≤i≤ ^q−₂¹ are pairwise non-isomorphic. There- fore, there are exactly ^q−₂¹ non-isomorphic edge-transitive Cayley graphs of Gof

valency 2k.

5 Proof of Theorem1.3

We first state a simple property about edge-transitive graphs. Recall that a permuta- tion groupP onΩ is called bi-transitive ifP has exactly two orbits onΩ and the two orbits have equal size.

Lemma 5.1 A graphΓ isX-edge-transitive if and only if one of the following two cases happens, whereαis a vertex:

1. Xα is transitive onΓ (α);

2. Xαis bi-transitive onΓ (α)with two orbitsΔ1andΔ2, and there existsσ∈^AutΓ such that(α, β)^σ=(γ , α)whereβ∈Δ₁andγ∈Δ₂.

As before, letG=Zp^d:Zq be a Frobenius group, wherep, qare odd primes. Let Γ be a connected undirected Cayley graphs ofGof valency at most 2q. Denote byα the vertex ofΓ corresponding to the identity ofG. LetX^AutΓ containG. Thenˆ we haveX= ˆGXα.

Lemma 5.2 Assume thatqdivides|X_α|. ThenΓ is edge-transitive and of valency 2q.

Proof Sinceq divides|Xα|, it follows thatZqXα^{Γ (α)}. ThusXα has an orbitΔof size at leastq. Forβ∈Δ, we haveβ^Xα =Δ. Define a graphΓ0:=(V , E0), where E₀= {α, β}^X. LetΣ be a connected component ofΓ₀ which containsα. Then the vertex setV Σis a subgroup ofG, and so|V Σ|dividesp^dq. LetY=^AutΣ. Thenq divides|Y_α|. It follows that the valency ofΣis at leastq, and hence|V Σ|> qandp divides|V Σ|. Moreover,Σ isY-edge-transitive. By Lemma5.1,Y_α is transitive or bi-transitive onΣ (α).

Assume that|Σ (α)|<2q. If Y_α is bi-transitive onΣ (α), then the two orbits of Y_α onΣ (α)have equal size which is at leastq, which is not possible. ThusY_α is transitive onΣ (α). Suppose thatY_α is imprimitive onΓ (α). ThenΓ (α)has aY_α- invariant partitionBwhich has l blocks and each block has sizem. Thus,q |l, or q|m, which is not possible sincelm= |Γ (α)|<2q. SoY_α is primitive onΓ (α).

LetN be the maximal intransitive normal subgroup of Y. LetB be the set ofN- orbits onV Σ, and letKbe the kernel ofY onB. SinceY_αis primitive onΣ (α)and

|V Σ| is odd, it follows thatΣ is a cover of Σ_N, and K_α=1. Thus,K=N, and Y :=Y /K^AutΣ_N. NowY is quasiprimitive onB. By Lemmas2.2,2.3and 2.5, Y is almost simple, and lies in Table2or3. SinceΣ_Nhas valency less than 2qandq divides|Y_α|, we conclude that this is not possible.

Therefore,Σis of valency 2q, and soΓ =Σis edge-transitive.

Moreover, we have a characterization of the valency 2qcase.

Lemma 5.3 LetΓ be a connected edge-transitive of valency 2q. Then the following statements hold:

(1) AutΓ = ˆabˇ: ˆbbτˇ ∼=Z_p^d_q:Z2q, whereτ is an involution, and τ:

aˆbˇ→(aˆb)ˇ ⁻¹, bˆbˇ→ ˆbb.ˇ

(2) AutΓ has exactly ^q−₂¹non-conjugate subgroups which are isomorphic toHand regular onV:

ˆa:bˆbˇ^j , 2≤j≤q+1 2 . (3) Ifq≥5, thenΓ is not a CI-graph.

Proof IfΓ =Σ[Kq], as in part (v) of Theorem1.1, thenΣ is of valency divisible byq. HenceΓ has valency divisible byq², which is a contradiction sinceq >2. It is easily shown that none of the graphs in parts (i)–(ii) of Theorem1.1has valency 2q. Thus, part (iii) or (iv) of Theorem1.1is satisfied.

Suppose thatGˆ is normal inX=^AutΓ. WriteΓ =^Cay(G, S), where|S| =2q. By Lemma4.1,X= ˆG:^Aut(G, S). Since(2q, p)=1, by Lemma4.2,Aut(G, S)is isomorphic to a subgroupZp−1. Further,Aut(G, S)is faithful onS, andS contains at least one element of orderqsinceS =G. ThusAut(G, S)≤Z2q. IfAut(G, S)= Z2q, then each elementz∈Sis conjugate toz⁻¹underAut(G, S), which is not pos- sible because an element ofGof orderq is not conjugate to its inverse. Therefore,