Finite vertex-primitive and vertex-biprimitive 2-path-transitive graphs

DOI 10.1007/s10801-011-0333-1

Finite vertex-primitive and vertex-biprimitive 2-path-transitive graphs

Cai Heng Li·Hua Zhang

Received: 6 February 2011 / Accepted: 16 November 2011 / Published online: 3 December 2011

© Springer Science+Business Media, LLC 2011

Abstract This paper presents a classification of vertex-primitive and vertex-biprim- itive 2-path-transitive graphs which are not 2-arc-transitive. The classification leads to constructions of new examples of half-arc-transitive graphs.

Keywords Symmetric graphs·2-path-transitive graphs·Half-transitive graphs

1 Introduction

LetΓ =(V , E)be a graph with vertex setV and edge setE. Recall that an arc is an ordered pair of adjacent vertices. Each edge{α, β}corresponds to two arcs(α, β) and(β, α). A 2-arc inΓ is a triple(α, β, γ )of three distinct vertices such thatβ is adjacent to bothαandγ. Identifying the 2-arcs(α, β, γ )and(γ , β, α)gives rise to a 2-path, denoted by[α, β, γ].

A graph Γ is called G-arc-transitive, (G,2)-arc-transitive, or (G,2)-path- transitive ifG≤^AutΓ acts transitively on the set of arcs, the set of 2-arcs, or the set of 2-paths, respectively, in which caseΓ is sometimes simply called a symmetric graph, a 2-arc-transitive graph, or a 2-path-transitive graph.

The study of symmetric graphs forms a significant part of current research efforts in algebraic graph theory. An important subclass of symmetric graphs is the class of

C.H. Li·H. Zhang (

School of Mathematics and Statistics, The University of Western Australia, Crawley, WA 6009, Australia

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

e-mail:[email protected]

H. Zhang

School of mathematics, Yunnan Normal University, Kunming 650091, P.R. China

2-arc-transitive graphs, the study of which has been a topic of active research for al- most half a century, see [3,8,11,17,18] and the references therein. It follows from the definition that a 2-arc-transitive graph is 2-path-transitive, and 2-arc-transitive graphs thus form a subclass of the class of 2-path-transitive graphs. In 1996, Conder and Praeger initiated the study of 2-path-transitive graphs. This study was further de- veloped in [12]. Apart from being a natural generalization of 2-arc-transitive graphs, this broader class of graphs is worth studying for several other reasons.

Recall that a graph Γ =(V , E) is called half-arc-transitive (or half-transitive) ifAutΓ is transitive onV andE, but not on the set of arcs. The class of half-arc- transitive graphs has been widely studied in the past twenty years, and a substantial amount of work was devoted to constructing new half-arc-transitive graphs. Our main motivation for studying 2-path-transitive graphs comes from the fact that there is a close relationship between 2-path-transitivity and half-arc-transitivity. It is shown in [12] that the line graphs of 2-path-transitive but not 2-arc-transitive graphs are half- arc-transitive. This link provides a method of constructing half-arc-transitive graphs.

Furthermore, it naturally leads to investigating the gap between ‘2-path-transitive’

and ‘2-arc-transitive’ in general. It is therefore useful to study 2-path-transitive graphs which are not 2-arc-transitive.

On the other hand, the concept of 2-path-transitive graphs may also be viewed as a generalization of cubic arc-regular graphs, another class of graphs that has re- ceived extensive attention in the literature. Here a graphΓ is called arc-regular (or 1-regular) ifAutΓ acts regularly on the set of arcs. It is easy to see that arc-regular cu- bic graphs are precisely cubic graphs that are 2-path-transitive but not 2-arc-transitive.

Therefore the line graphs of cubic arc-regular graphs are half-arc-transitive of va- lency 4. Based on this observation, a study of arc-regular cubic graphs was carried out in [16], which provides a generic method for constructing half-arc-transitive graphs of valency 4. The process in turn stimulates a further study on arc-regular graphs.

We note that a 2-path-regular graph is not 2-arc-transitive. Here a graphΓ is called 2-path-regular ifAutΓ acts regularly on the set of 2-paths ofΓ. The concept of 2-arc- regular graphs is similarly defined, and 2-arc-regular graphs are studied in [8,13], for example. As a special case of 2-path-transitive graphs, the study of 2-path-regular graphs is clearly an extension of that of 2-arc-regular graphs.

The aim of this paper is to classify vertex-primitive and vertex-biprimitive 2-path- transitive graphs which are not 2-arc-transitive, and then to apply the classification to construct new examples of half-arc-transitive graphs.

In this paper our conventions for expressing the structure of groups run as follows.

IfHandKare groups, thenH.Kdenotes any extension ofHbyK,H:Kdenotes a split extension ofHbyK, and the symbol[m]denotes an arbitrary group of orderm.

Furthermore, we use the symbols Th, B and M to denote the Thompson simple group, the Baby Monster simple group and the Monster simple group, respectively.

For the vertex-primitive case, the result is given in the following theorem. (A graph Γ =(V , E)is calledG-vertex-primitive ifG≤^AutΓ is primitive on vertex setV.) Theorem 1.1 Let Γ be a G-vertex-primitive, (G,2)-path-transitive graph of va- lencyk. Assume thatΓ is not(G,2)-arc-transitive. Thenk=p^e≡3(mod4)withp prime, and one of the following holds:

(i) G=Z^d₂:G_α, whereG_α is a 2-homogeneous permutation group of degreep^e. (ii) G=PSL2(p^e), andΓ =^Kp^e+1.

(iii) G=Ap,G_α=Zp:Z(p−1)/2, andk=pwithp=7,11,23. Furthermore, either AutΓ =ApandΓ is 2-path-regular, orAutΓ =SpandΓ is 2-arc-regular.

(iv) AutΓ =Gis a sporadic simple group,Γ is 2-path-regular, and(G, Gα)lies in the following table:

G Th B M

G_α Z31:Z15 Z47:Z23 Z59:Z29orZ71:Z35

A permutation groupGonΩis said to be biprimitive ifΩ has aG-invariant par- titionΩ=Δ1∪Δ2, such that the setwise stabilizerGΔ_i is primitive onΔi. A graph Γ =(V , E)is calledG-vertex-biprimitive ifG≤^AutΓ is biprimitive on the vertex setV.

Theorem 1.2 LetΓ be a connected(G,2)-path-transitive graph of valencykwhich is not(G,2)-arc-transitive. Assume further thatΓ isG-vertex-biprimitive. ThenΓ is bipartite,k=p^e≡3(mod4)withpprime, and one of the following holds:

(1) Γ is the standard double cover of a vertex-primitive graph as given in Theo- rem1.1.

(2) G=(Z^dr:Gα):Z2, whereris prime,d≥1, andGα is a 2-homogeneous permu- tation group of degreep^eand is an irreducible subgroup of GLd(r).

(3) Γ =^Kp^e,p^e, andG=(Z^e_p×Z^e_p):G_αβ:Z2, whereG_αβ≤ΓL1(p^e)×ΓL1(p^e).

(4) AutΓ =G=Sp,G_α=Zp:Z(p−1)/2, wherep≡3(mod4)is prime,p=7, 11, 23, andΓ is 2-path-regular.

(5) G=PGL3(4).Z2,Gα=(Z7:Z3)×Z3,k=7,AutΓ =^Aut(PSL3(4))=G.2, and Γ is 2-arc-transitive.

(6) AutΓ =G=PΓU3(5),G_α=(Z7:Z3)×Z3, andk=7.

Applying the classification result of Theorems1.1and1.2, we construct half-arc- transitive graphs in Theorem1.3. Some of these graphs are new.

Theorem 1.3 For each groupGand a subgroup H < Gin Table1, there exists a half-arc-transitive graphΣof valencymsuch that^AutΣ=GandHis the stabilizer inGof some vertex ofΣ.

This paper is organised as follows: examples of the graphs given in these three theorems are constructed in Sect.2. A reduction is given in Sect.3for the proofs of Theorems1.1and1.2, and finally Theorems1.1and1.2are proved in Sect.4.

2 Examples

In this section, we construct and study examples of 2-path-transitive graphs given in Theorems1.1and1.2. Recall that a permutation groupGonΩ is called 2-transitive

Table 1 Pairs(G, H ) associated with half-transitive- graphs

G H m

PΓU₃(5) Z²₃:Z2 12

Th Z15:Z2 60

B Z23:Z2 92

M Z29:Z2 116

Z35:Z2 140

A_p D_p−1 2(p−1), wherep≡3(mod4)is prime, and p=7,11 or 23

S_p D_p−1 2(p−1),pis as above

or 2-homogeneous ifGinduces a transitive action on the set of ordered pairs or on the set of 2-subsets ofΩ, respectively.

LetGbe a finite group, and letHbe a core-free subgroup ofG. Denote by[G:H] the set of right cosets ofH inG, namely[G:H] = {H x|x∈G}. For an element g∈Gwithg²∈H, the Sabidussi coset graph ofGwith respect toH andgis the graph with vertex set[G:H], such thatH xandH yare adjacent if and only ifyx⁻¹∈ H gH. This coset graph isG-arc-transitive and is denoted byCos(G, H, H gH ).

Assume thatΓ =^Cos(G, H, H gH )is a(G,2)-path-transitive graph which is not (G,2)-arc-transitive. Denote by α,β the vertices corresponding toH andH g, re- spectively. Then(α, β)^g=(β, α), andg²∈G_α. By [4, Theorem 2],G_α =H is 2- homogeneous but not 2-transitive on the neighborhood ofα, and furthermore, |G_α| is odd. Thusg²=1, that is, gis an involution. AlsoΓ is connected if and only if H, g =G.

To construct 2-path-transitive graphs which are not 2-arc-transitive, we need the following result, the proof of which is straightforward.

Lemma 2.1 LetGbe a finite group with a core-free subgroupHand an involutiong.

Assume further thatH, g =G, and the coset action ofH on[H:H∩H^g]is 2- homogeneous but not 2-transitive. Then the coset graphCos(G, H, H gH )is(G,2)- path-transitive but not(G,2)-arc-transitive.

Example 2.2 Let Γ =^Kq+1, where q =p^e ≡3(^mod 4), with p prime. Then Aut(Γ )=Sq+1 contains a subgroup G=PSL2(q). For a vertex α of Γ, we have G_α =Z^e_p:Z(p^e−1)/2, which is a maximal subgroup of G. Thus by Lemma 2.1, the graph Γ is G-vertex-primitive, and (G,2)-path-transitive but not (G,2)-arc- transitive.

Example 2.3 LetΓ =^Kp^e,p^e, wherep^e≡3(mod4), be the complete bipartite graph of order 2p^e. Then ^Aut(Γ )=Sp^e Z2. Let G=((Z^ep ×Z^ep):H ):Z2<Aut(Γ ), whereZ(p^e−1)/2≤H≤ΓL1(p^e), and |H| is odd. Then the graphΓ isG-vertex- biprimitive,(G,2)-path-transitive but not(G,2)-arc-transitive. The index two sub- groupG⁺ofGfixes both parts ofΓ, and is primitive of affine type.

Next, we study a family of 2-path-transitive graphs associated with alternating groups.

Example 2.4 LetG=Sp, andT =Ap, both acting naturally on the set{1,2, . . . , p}, wherepis prime, such thatp≡3(mod4), withp=7,11,23. LetHbe a subgroup ofT isomorphic toK:L, where K=Zp andL=Z(p−1)/2. Then H is a maximal subgroup ofT. Since subgroups which are isomorphic toH are conjugate inT, it follows thatLis conjugate tot² , wheretis a(p−1)-cycle. Letg∈NT(L)\L, and f∈NG(L)\Apbe involutions. Define

Γ =Cos(T , H, H gH ) and Σ=Cos(G, H, Hf H ).

For example, we may chooset=(1,2, . . . , p−1). Then t²=(1,3, . . . , p−2)(2,4, . . . , p−1), andgandf can be defined as follows:

g=(3, p−2)(5, p−4) . . . p−1

2 ,p+3 2

(4, p−1)(6, p−3) . . . p+1

2 ,p+5 2

∈Aq,

f =(1,2)(3,4) . . . (p−2, p−1)∈Sq\Aq.

The graphΓ is connected,(T ,2)-path-transitive but not(T ,2)-arc-transitive, and AutΓ =T orG; see [12] for details. Further, sinceH is a maximal subgroup ofT, Γ is alsoT-vertex-primitive.

For the graphΣ, we have the following conclusion.

Lemma 2.5 LetΣbe the graph constructed in Example2.4. ThenΣis connected, vertex-biprimitive, and 2-path-regular; furthermore,AutΣ=Sp.

Proof By definition,f ∈G\T normalizesL. SinceH < T, andG/T ∼=Z2,T has exactly two orbits on[G:H], say Δ1 andΔ2, such thatG⁺: =GΔ_i =T. More- over, the setwise stabilizerG⁺ is primitive onΔ_i, andΣ is a bipartite graph with partsΔ₁ and Δ₂. Since f does not normalize H, it follows that Σ is connected.

SinceH∩H^f =L, and the action ofH on[H:H∩H^f]is 2-homogeneous but not 2-transitive, we conclude thatΣis a(G,2)-path-transitive graph of valencyp, which is not(G,2)-arc-transitive. Further,Γ isG-vertex-biprimitive.

Suppose thatG⁺is not normal inAutΣ. Then there exists a groupX such that T < X≤^AutΣ, and NAutΣ(T )is a maximal subgroup of X. Since T is primitive onΔ_i, so isX. Since|Δ_i| = |T :H| =(p−2)!, by the O’Nan-Scott Theorem, we conclude that eitherX is almost simple orXAp−2×Ap−2. Moreover, because the order |X| is divisible by p, it follows thatX is almost simple. Thus we have X=NAutΓ(T )X_α is a maximal factorisation of the almost simple groupX. There- fore the triple(X,NAutΓ(T ), X_α)should lie in the classification of [15]. However, an inspection shows that there is no such a triple, which is a contradiction. ThusG⁺=T is normal inAutΣ. SinceT is primitive onΔ_i, the centralizer ofT inAutΣis trivial, soAutΣ≤^Aut(T )=Sp. SinceAutΣ≥G=Sp, we haveAutΣ=Sp.

LetΓ =^Cos(G, H, H gH ), and letAut(G, H )= {σ ∈^Aut(G)|H^σ =H}. The following conclusion is well-known, and the proof is easy.

Lemma 2.6 Suppose thatσ ∈^Aut(G, H ). ThenΓ =^Cos(G, H, H gH )is isomor- phic toΣ=^Cos(G, H, H g^σH ). Moreover,σ induces an automorphism ofΓ if and only ifH gH =H g^σH.

LetΓ be the graph andtbe a(p−1)-cycle defined in Example2.4. LetM= t . We point out that the choice of g for defining Γ is not unique. Indeed we can even choose g such that g∈ NT(L)\NT(M). This is because NT(L) is an in- dex two subgroup of NG(L), and further, as NT(M)≤NT(L), and (p−1)/2 is odd, we have NG(M)=M:^Aut(M)∼=Zp−1:^Aut(Zp−1)=Zp−1:^Aut(Z(p−1)/2). Since NT(L)≥Zp−1:(Aut(Z(p−1)/2)×^Aut(Z(p−1)/2)), we conclude that NT(M) <NT(L), and a Sylow-2 subgroup of NT(M)is properly contained in a Sylow-2 subgroup of NT(L). Therefore there exists a 2-elementgsuch thatg∈NT(L)\NT(M). Actually the full automorphism group ofΓ depends on the choice ofg.

The caseAutΓ =Spdoes occur.

Lemma 2.7 Ifg∈NT(M)\M, thenAutΓ =SpandΓ is 2-arc-regular.

Proof LetH₁=K:M, and letV₁= [G:H₁]. ThenHis an index 2 subgroup ofH₁. Now the graphΓ₁=Cos(G, H1, H₁gH₁)is 2-arc regular, with full automorphism group Sp(see [8, Lemma 4.2]). Further, sinceT is transitive onV₁, for anyH₁x∈V₁ we may choosex∈T. Then it is straightforward to show that the mapψ:V₁→V defined byψ (H1x)=H xis a graph isomorphism betweenΓ1andΓ. It follows that

AutΓ =Sp, andΓ is 2-arc-regular.

The caseAutΓ =Apoccurs too.

Lemma 2.8 Ifg∈NT(L)\NT(M), thenAutΓ =ApandΓ is 2-path-regular.

Proof As indicated in Example2.4,AutΓ =Ap or Sp. Suppose that AutΓ =Sp. WriteM=L× σ , where o(σ )=2. Then Ap, σ =Sp andH^σ =H. Thus by Lemma2.6, we haveH gH=H g^σH. Sinceg /∈NT(M), we obtaing^σ =g. Since g^σ ∈H gH andg∈NT(L), there exista,b∈K andu∈L such thatg^σ =agbu.

Aso(g^σ)=2, we have (agbu)²=1, so(bua)^g=(bua)⁻¹. Since bua∈H, we obtainbua∈H∩H^g=L. Asu∈NT(K), we haveu⁻¹bua=b^ua∈K∩L, that is, b^ua=1. Thusg^σ=(gu)^a−1. Sinceg^σ normalizesL, we have(L^a)^gu=L^a. Notice thatL^a∈H, soL^a≤H∩H^gu=L, and thereforeL^a=L. Ifa=1, then the order of aisp, which means thatK normalizesL, which is a contradiction. Thusa=b=1 andg^σ =gu. Since bothg and σ are involutions, we obtain σ^g=uσ, that is,g normalizesM, which is again a contradiction. ThusAutΓ =Ap, as claimed.

The graphs in the next example arise from three sporadic simple groups: the Thompson group Th, the Baby Monster B, and the Monster M.

Example 2.9 LetG=Th, B or M. Then by the Atlas [5], the groupGcontains a maximal subgroupH such thatH ∼=Zp:Z(p−1)/2, wherep=31 forG=Th, p= 47 for G=B, and p=59 or 71 for G=M. Let L be a subgroup of H which is isomorphic toZ(p−1)/2. Then in each case, NG(L) is of even order. This is true because the Atlas [5] shows that forG=Th,|CG(L)| =30; forG=B,|CG(L)| = 46; forG=M withp=59, NG(L)=(Z29:Z14×3).2; and forG=M withp=71,

|CG(L)| =70 or 2100.

Letgbe an involution in NG(L), and letΓ =^Cos(G, H, H gH ). ThenH∩H^g= L, hence Γ has valency|H:L| =p. Since H is a maximal subgroup of G, we haveH, g =G, thus Γ is connected. Further, since the action ofH on [H:L] is 2-homogeneous and is not 2-transitive, we conclude thatΓ isG-vertex-primitive, (G,2)-path-transitive but not(G,2)-arc-transitive.

Moreover, for the graphs that we just constructed in Example2.9, the following conclusion is true:

Lemma 2.10 If Γ is a graph in Example 2.9, then^AutΓ =G, andΓ is 2-path- regular.

Proof Suppose thatGis not normal in^AutΓ. Then there exists a groupXsuch that G < X≤^AutΓ and NAutΓ(G)is a maximal subgroup ofX. SinceGis primitive on V Γ, so isX. Also becauseΓ is(G,2)-path-transitive, we have eitherΓ is(X,2)- arc-transitive, orΓ is (X,2)-path-transitive but not (X,2)-arc-transitive. Thus the primitive type ofXis affine, almost simple, product action or twisted wreath product.

Notice that|V Γ| = |G:H|is not a power of an integer, and|G:H|is exactly divisible by 19, we conclude thatX is almost simple. ThusX=NAutΓ(G)Xα is a maximal factorisation, and hence the triple(X,NAutΓ(G), Xα)lies in the classification given in [15]. However, an inspection of the classification shows that there is no such a triple, which is a contradiction. ThereforeGis normal inAutΓ. SinceGis primitive onV, the centralizer ofGinAutΓ is trivial. AsOut(G)=1, we conclude thatAutΓ =

G, andΓ is 2-path-regular.

The following two examples arise from classical groups of Lie type.

Example 2.11 Let T =PGL3(4). Then by the Atlas [5], T contains a maximal subgroupH which is isomorphic to (Z7:Z3)×Z3. Let G=PGL3(4).τ , where τ is a field automorphism or the graph automorphism of PSL3(4), of order 2.

Write H =K :L=(x :y )× z , where K = x , L= y × z , o(x)=7, o(y)=o(z)=3, and zis a diagonal automorphism of PSL3(4). Since subgroups ofGwhich are isomorphic toHare conjugate, we may assume thatx, y∈PGL3(2).

Thenzx=xzandzy=yz. By the Atlas [5], NG(K)=(7:3×3).2. Sincexy=yx, we have|CG(K)| =21 or 42. If|CG(K)| =42, then NG(K)contains only three in- volutions. Assume that|CG(K)| =21. Then NG(K)/CG(K)=Z6. Thus there are at most 21 involutions in NG(K). Suppose thata∈NG(K)is an involution such that a∈NG(L). We claim that none of the involutionsa^xk, where 1≤k≤6, is contained in NG(L). Assume thata^xk ∈NG(L). Thenaa^xk∈NG(L). By definition,x, a is a

dihedral group of order 14, and soaa^xk has order 7. Since|NT(L)| =27, we have

|NG(L)|is 27 or 54. Since|NG(L)|is even, we have|NG(L)| =54. But 7|NG(L)|, a contradiction. It follows that among the involutions of NG(K), at most three are contained in NG(L). Thus there exists an involution g∈NG(L)\NG(K), and the graphΓ =Cos(G, H, H gH )isG-vertex-biprimitive,(G,2)-path-transitive but not (G,2)-arc-transitive, of valency 7.

Example 2.12 LetT =PGU3(5). Then by the Atlas [5],T contains a maximal sub- groupH which is isomorphic to (Z7:Z3)×Z3. Let G=PΓU3(5). As in Exam- ple2.11, writeH=K:L. Then by GAP [9], NG(L)contains nine involutions, three of which are contained in NG(K). Thus for any 2-elementg∈NG(L)\NG(K), the graphΓ =Cos(G, H, H gH )isG-vertex-biprimitive,(G,2)-path-transitive but not (G,2)-arc-transitive, of valency 7.

For the graphs in Examples2.11and2.12, the full automorphism groups of the graphs are determined in the next two lemmas.

Lemma 2.13 IfΓ is the graph in Example2.11, thenAutΓ =PSL3(4).(2×S3)and Γ is 2-arc-transitive.

Proof By definition,G=PGL3(4).τ , whereτ is a field automorphism or the graph automorphism of PSL3(4), of order 2. Assume first thatτ is the graph automorphism of PSL3(4)(that is,τ is the transpose inverse map). NowΓ =^Cos(G, G_α, G_αgG_α), withG_α =7:3×3. Let T =PGL3(4)and consider G_α as a semi-direct product K:L=(x :y )× z , whereK= x ,L= y × z ,o(x)=7, o(y)=o(z)=3, and z is a diagonal automorphism of PSL3(4). Then the 2-element g lies in NG(L)\NG(K).

Letσ be a field automorphism of PSL3(4). We claim thatg^σ ∈H gH.

As observed in Example2.11, the normaliser NT(L)is a Sylow 3-subgroup ofG, with|NT(L)| =27 and|NG(L)| =54. Thus we may write NT(L)=(y × z ):t , whereo(t )=3. Thengcan be written asg=g1τ, whereg1=y^k1z^k2t^k3 ∈T, with k_i= ±1. As bothgandτ normalizeL, so doesg1. Sinceτ normalizesH, we have H gH=H g1τ H=H g1H τ. Becauseσ τ=τ σ, we haveg^σ=g^σ₁τ, and henceg^σ∈ H gH=H g1H τ if and only ifg₁^σ ∈H g1H. By the Atlas [5],σ fixes the Sylow 3- subgroup NT(L), and thusg₁^σ∈NT(L). Assume thatg₁^σ=y^l1z^l2t^l3=y^l1z^l2t^l3−k3t^k3. Sincet normalizesy × z , it follows thatg₁^σ ∈H g₁H. Thusσ induces an auto- morphism of Γ. If we interchange the roles of τ and σ by assuming thatτ is a field automorphism of PSL3(4), andσ is the graph automorphism, then analogously we haveσ ∈^AutΓ. Hence in both cases, we have AutΓ ≥PGL3(4).(τ × σ )∼= PSL3(4).(2×S3). We will show that equality holds. LetA=PSL3(4).(2×S3).

Suppose, to the contrary, thatX₀:=^AutΓ > A. Then there exists a subgroupXof X₀such thatA < X≤X₀andAis maximal inX. We have two possibilities:X is primitive or biprimitive onV.

Assume thatXis primitive onV. ThenΓ is(X,2)-path-transitive. Accordingly, the primitive type of X is either affine, almost simple, product action, or twisted wreath product. Assume first thatX is of affine type. Then for any α∈V, X_a is

faithful onΓ (α). On the other hand, Aα ≤X_α, and Aα acts unfaithfully onΓ (α), we obtain a contradiction. Since|V| =1920, we know that the primitive type of X is neither product action nor twisted wreath product. Thus X is almost simple, andX=AX_α is a maximal factorisation. Hence the triple (X, A, X_α) lies in the classification given in [15]. Notice that|V| = |X:X_α| =1920. An inspection of the classification shows that there is no such a triple, which is a contradiction.

Assume thatX is biprimitive onV. Then the two invariant blocks ofX are the same as that ofG, which we suppose to beΔandΔ. ThenX induces a primitive action on bothΔandΔ. Since|V| =1920, the primitive type ofXis not affine, prod- uct action, or twisted wreath product. ThusX_Δis almost simple, and once again we obtain a maximal factorisationX_Δ=(A∩X_Δ)(X_Δ)_α, whereA∩X_Δ=PGL3(4).2.

An inspection of [15] shows that there is no such a factorisation, a contradiction.

From the above discussion, we come to the conclusion thatAutΓ =PSL3(4).(2× S3), andΓ is 2-arc-transitive, as claimed.

Lemma 2.14 LetΓ be the graph in Example2.12. Then AutΓ =G, and Γ is 2- path-transitive but not 2-arc-transitive.

Proof Since^AutΓ ≥G, we only need to show that equality holds. Suppose, on the contrary, that X0:=^AutΓ > G. Then there exists a subgroup X of X0 such that G < X≤X₀, and Gis maximal inX. In this case we have |V| =12000, and the argument in Lemma2.13also applies to the current case. Thus^AutΓ =G.

3 A reduction

For a graphΓ =(V , E)and a vertexα, denote byΓ (α)the neighborhood ofα, that is, the set of vertices to whichαis adjacent. For a groupG≤^AutΓ, the stabilizerG_α induces a natural action onΓ (α). As usual, the permutation group induced byG_αon Γ (α)is denoted byG^{Γ (α)}_α , and the kernel ofG_α acting onΓ (α)is denoted byG^[_α^1]. ThenG^{Γ (α)}_α ∼=G_α/G^[_α^1]. LetΓ be(G,2)-path-transitive. Then by the well-known Thompson–Wielandt Theorem, for an arc(α, β)ofΓ, the subgroupG^[_αβ^1]=G^[α^1]∩ G^[_β^1]is ap-group withpprime. Moreover, it follows from a result of Weiss (see [18]) thatG^[_αβ^1]=1. A characterisation of the vertex stabilizer for a 2-path-transitive graph is then easily obtained in [12], restated below. Recall that for a groupXand a prime p, Op(X)is the largest normalp-subgroup ofX.

Theorem 3.1 (see [12, Theorem 1.1]) Let Γ be a connected(G,2)-path-transitive graph which is not (G,2)-arc-transitive. Then Γ has valency p^e, where p^e ≡ 3(mod 4) with p prime, and for each edge {α, β}, G^{Γ (α)}_α ≤ AΓL1(p^e) is 2- homogeneous, and the following hold:

(a) G^[_β^1] ∼=(G^[_β^1])^{Γ (α)}G^{Γ (α)}_αβ ≤Z(p^e−1)/2:Ze < ΓL1(p^e), and Gαβ =(G^[α^1]× G^[_β^1]).O, whereO∼=G^{Γ (α)}_αβ /(G^[_β^1])^{Γ (α)}.

(b) Op(G_α)∼=Z^e_p is regular on Γ (α), and G_α =Op(G_α):G_αβ, with order |G_α| dividingp^e(^(pe−₂^1)e)².

For positive integersqandn, a prime divisor ofqⁿ−1 is called a primitive prime divisor if it does not divideqⁱ−1 for alli < n. The following result is due to Zsig- mondy.

Lemma 3.2 (Refer to [10, p. 508]) For any positive integersqandn, either (i) qⁿ−1 has a primitive prime divisor, which is at leastn+1, or

(ii) (n, q)=(6,2)or(2,2^b−1), whereb≥2 is an integer.

For a prime-powerp^e≡3 (mod4), it is easily shown thatp^e−1 has primitive prime divisors. We thus have the following statement.

Corollary 3.3 If p^e is the valency of a 2-path-transitive but not 2-arc-transitive graph, thenp^e−1 has a primitive prime divisor which is at least 5.

LetΓ =(V , E)be a connected(G,2)-path-transitive graph which is not(G,2)- arc-transitive. Assume further thatGis primitive or biprimitive onV. Let

G⁺= G_α|α∈V .

Then eitherGis primitive onV andG⁺=G, orGis biprimitive onV, andG⁺is of index 2 inGand has exactly two orbits onV which form the bipartition ofV. In particular, in either case,G_α=G⁺_α is maximal inG⁺. The next lemma is a reduction for proving Theorems1.1and1.2.

Lemma 3.4 LetΓ =(V , E)be a connected(G,2)-path transitive graph which is not(G,2)-arc-transitive. Assume thatGacts primitively or biprimitively onV. Then eitherΓ =^Kp^e,p^e withp^e≡3(mod4), orG⁺is a primitive permutation group of affine type or almost simple type.

Proof LetΩ be an orbit ofG⁺onV, and letα∈Ω. By Theorem3.1, the valency

|Γ (α)|isp^efor some primepsuch thatp^e≡3(mod4).

Suppose thatG⁺acts unfaithfully onΩ. ThenΓ is bipartite with two partsΩand Ω^g, whereg∈G\G⁺. SinceG⁺is faithful onV =Ω∪Ω^g, the kernelG⁺_(Ω)acts onΩ^gnon-trivially. SinceG⁺_(Ω)G⁺andG⁺is primitive onΩ^g, we conclude that G⁺_(Ω)is transitive onΩ^g. It follows thatΓ is a complete bipartite graphK_|Ω|,|Ωg|, of valency|Ω|, and hence|Ω| =p^e.

Assume instead thatG⁺ is faithful onΩ. SinceGis primitive or biprimitive on V, we haveG⁺≤Sym(Ω)is primitive. By Theorem3.1, the point stabilizerG⁺_α is soluble, and hence in the language of the O’Nan-Scott Theorem (see [7]), the action ofG⁺onΩ is of affine, almost simple, or product action type.

Suppose thatG⁺is of product action type. ThenG⁺≤(T˜1× ˜T2× · · · × ˜Tk):Sk

≤Sym(Δ)Sk, andΩ=Δ^k, wherek≥2,T˜i≤Sym(Δ)is almost simple with socle Ti, andT˜i is primitive onΔ. The socle,N=^soc(G⁺)=T1× · · · ×Tk∼=T^k, where T_i∼=T, is a minimal normal subgroup ofG⁺. SinceG⁺=N G⁺_α, we know thatG⁺_α induces a transitive action on{T₁, T₂, . . . , T_k}by conjugation. Since G⁺_α is of odd order, it follows thatkis odd and sok≥3.

By Theorem3.1, the subgroup Op(G_α)∼=Z^e_pis regular onΓ (α)and is a minimal normal subgroup ofG_α. Thus either Op(G_α)≤N_α, or Op(G_α)∩N_α=1. Further, sinceNαis transitive onΓ (α), the order|Nα|is divisible byp^e. If Op(Gα)∩Nα= 1, then |Gα| is divisible by (p^e)², which is not possible by Theorem 3.1. Thus Op(G_α)≤N_α, andN_α=Op(G_α):N_αβG_α.

Note thatZ^e_p:N_αβ=Op(G_α):N_αβ=N_α =

T_iδi, whereδ_i ∈Δ. Suppose that N_αβ=1. ThenT_iδi =Z^mp (for somem dividing e) is a maximal subgroup of the almost simple groupT˜i, which is impossible. HenceNαβ=1. Since Op(Gα)∩Nαβ= 1, there exists a primet=pwhich divides|N_αβ|. This primet divides|T_iδi|, and it follows thatN_αcontains a subgroup which is isomorphic toZ^k_t. A Sylowt-subgroup ofN_α is isomorphic to a Sylowt-subgroup ofN_α/Op(G_α), which is isomorphic to a subgroup ofG_αβ=(G^[_α^1]×G^[_β^1]).O. Since bothG^[_α^1]andG_αβ/G^[_α^1]are subgroups ofΓL1(p^e)which are metacyclic, it follows thatk≤4, and sok=3.

LetLbe the kernel ofG⁺acting on{T₁, T₂, T₃}by conjugation. ThenT₁×T₂× T₃=NL≤ ˜T₁× ˜T₂× ˜T₃, whereT_i≤ ˜T_i≤^Aut(T_i)such thatT˜_i∼=L/CL(T_i). Since T1, T2, T3are conjugate inG⁺, we haveT˜1∼= ˜T2∼= ˜T3. Each elementg∈Lcan be written as

g=(t1, t2, t3), for someti∈ ˜Ti.

Let π_i be the projection from L to the ith coordinate, namely π_i(g)=t_i. Then π_i(L)∼= ˜T_i.

NowX: =(T˜1× ˜T2× ˜T3)≤Sym(Δ)S3, and hence for a pointα=(δ1, δ2, δ3)∈ Ω, the stabilizerXαisT˜1δ₁× ˜T2δ₂× ˜T3δ₃. Sinceπi(L)= ˜Ti, we haveπi(Lα)= ˜Tiδ_i. By Lemma3.2,p^e−1 has a primitive prime divisorr≥5. Since(p^e−1)/2 divides

|G_α|, so doesr. Further, asG⁺_α/L_α∼=G⁺/L≤S3, we conclude thatr| |L_α|, and so rdivides| ˜Tiδ_i|.

By Theorem3.1,Z^e_p∼=Op(G_α)N_αG_α, and hence Z^l_p∼= π_i

Op(G_α)

π_i(N_α)∼=T_iδiT˜_iδi, wherel=e/3. We may writeT˜iδ_i=Z^lp:Ki. Thenrdivides|Ki|.

Let C_i be a Sylow r-subgroup of K_i, and consider the subgroup M_i: = π_i(Op(G_α)):C_i of T˜_i. If C_i acts non-trivially on π_i(Op(G_α))∼=Z^l_p, then C_i <

GLl(p), which contradicts the fact that rp^l−1. ThusM_i =π_i(Op(G_α))×C_i. Notice that a Sylow r-subgroup of G_α is contained in a Sylow r-subgroup of T˜1× ˜T2× ˜T3, it follows that all ther-elements ofGαare in the centralizer of Op(Gα), which isG^[_α^1]by Theorem3.1. Sincer does not divide |G^{Γ (α)}_α |, we again obtain a contradiction.

HenceG⁺is not of product action type, that is, the primitive type ofG⁺is affine

or almost simple.

4 Proofs of the main theorems

The remaining part of this paper is devoted to complete the proofs of our main theo- rems. The proofs of the Theorem1.1and Theorem1.2depend on the classification,

by Liebeck and Saxl [14], of primitive permutation groups of which the point stabi- lizer has odd order.

Theorem 4.1 [14, Theorem 2] LetGbe an almost simple group withT =^soc(G).

Assume thatMis a maximal subgroup ofGof odd order. Then one of the following holds:

(i) G=Ap, andM=Zp:Z(p−1)/2, wherep≡3(mod4)is a prime, andp=7,11 or 23;

(ii) T =PSL2(p^e), and T ∩M=Z^e_p:Z(p^e−1)/2, where p is a prime, and p^e≡ 3(mod4);

(iii) T =PSLr(q), andT ∩M=Z(q^r−1)/(q−1)(r,q−1):Zr, whereris an odd prime;

(iv) G=PSL3(4).3, andM=(Z7:Z3)×Z3;

(v) T =PSUr(q), andT ∩M=Z(q^r+1)/(q+1)(r,q+1):Zr, wherer is an odd prime, and(r, q)=(3,3),(5,2)or(3,5);

(vi) G=PSU3(5).3, andM=(Z7:Z3)×Z3. (vii) GandMlie in the following table:

G M23 Th B M

M Z23:Z11 Z31:Z15 Z47:Z23 Z59:Z29,Z71:Z35

As shown in the examples of the last section, almost all of the pairs(G, M)in The- orem4.1do give rise to(G,2)-path-transitive graphs which areG-vertex primitive orG-vertex biprimitive.

4.1 Proof of Theorem1.1

LetΓ be aG-vertex-primitive and(G,2)-path-transitive but(G,2)-arc-intransitive graph, of valencyk. ThenG_α is primitive onΓ (α), and by Theorem3.1,k=p^e≡ 3(^mod4)withpprime. By Lemma3.4, the primitive type ofGis affine or almost simple. Assume thatG is of affine type, with N: =^soc(G)=Zⁿp. Then we may identifyV Γ withN such thatα is the zero vector. Let β∈Γ (α). Then the pair {β,−β}is a block of imprimitivity inΓ (α)ofG_α. SinceG_α is 2-homogeneous on G_α, we haveβ= −β, sop=2, as in (1) of Theorem1.1. Assume thatGis almost simple, and T ≤G≤^Aut(T ), with T a non-abelian simple group. Then the pair (G, G_α)appears in Theorem4.1. Thus we need to analyse the pairs of Theorem4.1 in turn.

(1) Assume that (G, Gα)= (Ap,Zp:Z(p−1)/2), (Th,Z31:Z15), (B,Z47:Z23), (M,Z59:Z29), or(M,Z71:Z35), or(T , T_α)=(PSL2(p^e),Z^e_p:Z(p^e−1)/2). Then by Ex- amples2.2,2.4, and2.9, each of these cases corresponds to aG-vertex-primitive, (G,2)-path-transitive but not(G,2)-arc-transitive graph, as in Theorem1.1.

(2) Assume that (G, G_α) =(M23,Z23:Z11). We write G_α as K:L, where K∼=Z23, L∼=Z11. Then Gα is the normalizer of a Sylow-23 subgroup of M23. By the Atlas [5], the cyclic subgroups of order 11 form two conjugacy classes inG.

ForL∼=Z11, assume that the order|NG(L)|is even. Then NG(L)is contained in a maximal subgroup isomorphic to M11 or M22. Suppose that NG(L) < M, where

M is M11 or M22. Then it follows that NG(L)=NM(L), and by the Atlas [5], NM(L)=Z11:Z5, a contradiction. Thus there is no(G,2)-path-transitive but(G,2)- arc-intransitive graph occurring in this case.

(3) Assume that(T , T_α)=(PSLr(q),Z(q^r−1)/(q−1)(r,q−1):Zr). Definem=(q^r− 1)/(q−1)(r, q−1). Then

G_α=(Zm:Zr).o,

whereo=G/T. By Theorem3.1, the unique minimal normal subgroup ofGα is an elementary abelian group, somis a prime, andr=(m−1)/2. Notice that ifq=p^e withp≥3, then r < (m−1)/2. Thus p=2 and (r, q)=(3,4), and(G, G_α)= (PGL3(4),7:3×3). If there exists a 2-path-transitive and 2-arc-intransitive graph Γ, let(α, β)be an arc ofΓ. ThenΓ =Cos(G, Gα, GαgGα), with the 2-elementg interchangingαandβ. Assume thatG_α =(x :y )× z , whereo(x)=7,o(y)= o(z)=3, and z is a diagonal automorphism. ThenG^[_α^1]= z , G^[_β^1]= y , andg interchangesG^[α^1]withG^[_β^1]. Checking the Atlas [5],L:= y × z is contained in a subgroup isomorphic toZ²₃:2A4. Thusy∈Z²₃, andz∈2A4, but it is easy to see that no 2-element of 2A4interchangesy withz , a contradiction (actually by GAP [9], NG(L)=27). Thus in this case there exists no(G,2)-path-transitive but(G,2)-arc- intransitive graph.

(4) Assume that(T , T_α)=(PSUr(q),Z(q^r+1)/(q+1)(r,q+1):Zr). Then by a similar argument to the one above, the only possibility is (G, G_α)=(PGU3(5),7:3×3).

Denote by(x :y )× z the subgroup 7:3×3, whereo(x)=7,o(y)=o(z)=3, and letL= y × z . Using the “pq-package” of GAP [2], then calculation shows that|NG(L)| =27. Thus there exists no 2-elementgwhich satisfies the conditions of Lemma2.1, so no such graph exists.

This completes the proof of Theorem1.1.

LetΓ be a (directed or undirected) graph with vertex setV. Then the standard double cover ofΓ is defined to be the undirected bipartite graphΓ˜with partsV₀and V₁, whereV_i= {(v, i)|v∈V}, such that two vertices(x, i)and(y, j )are adjacent if and only ifi=j, andx,yare adjacent inΓ.

Lemma 4.2 Let Γ =^Cos(G, H, H gH )be a G-vertex-primitive, and(G,2)-path- transitive but(G,2)-arc-intransitive graph. LetΣ=^Cos(K, H₁, H₁(g, z)H₁), where K=G× z ,H1=H× {1}, andzis an involution. Then

(1) Σis isomorphic to the standard double cover ofΓ.

(2) ΣisK-vertex-biprimitive,(K,2)-path-transitive and(K,2)-arc-intransitive.

Proof (1) We haveV Γ = [G:H] = {H x|x∈G}. LetΓ˜ denote the standard double cover ofΓ. ThenVΓ˜= {(H x, i)|x∈G, i=0 or 1}. Define a mapψ:VΓ˜→V Σ as follows:

ψ

(H x, i)

=H₁ x, zⁱ

.