An infinite family of biquasiprimitive 2-arc transitive cubic graphs

DOI 10.1007/s10801-011-0299-z

An infinite family of biquasiprimitive 2-arc transitive cubic graphs

Alice Devillers·Michael Giudici·Cai Heng Li· Cheryl E. Praeger

Received: 2 March 2011 / Accepted: 6 June 2011 / Published online: 1 July 2011

© Springer Science+Business Media, LLC 2011

Abstract A new infinite family of bipartite cubic 3-arc transitive graphs is con- structed and studied. They provide the first known examples admitting a 2-arc tran- sitive vertex-biquasiprimitive group of automorphisms for which the index two sub- group fixing each half of the bipartition is not quasiprimitive on either bipartite half.

Keywords 2-arc-transitive graphs·Quasiprimitive·Biquasiprimitive·Normal quotient·Automorphism group

1 Introduction

The study of cubics-arc-transitive graphs goes back to the seminal papers of Tutte [14,15] who showed thats≤5. More generally, Weiss [16] proved thats≤7 for graphs of larger valency. In [13], the last author introduced a global approach to the study ofs-arc-transitive graphs.

Given a connected graphwith ans-arc-transitive groupGof automorphisms, if Ghas a nontrivial normal subgroupN with at least three orbits on vertices, thenG

The paper forms part of Australian Research Council Federation Fellowship FF0776186 held by the fourth author. The first author is supported by UWA as part of the Federation Fellowship project and the second author is supported by an Australian Research Fellowship.

A. Devillers (

Centre for the Mathematics of Symmetry and Computation, School of Mathematics and Statistics, The University of Western Australia, 35 Stirling Highway, Crawley WA 6009, Australia e-mail:alice.devillers@uwa.edu.au

M. Giudici

e-mail:michael.giudici@uwa.edu.au C.H. Li

e-mail:cai.heng.li@uwa.edu.au C.E. Praeger

e-mail:cheryl.praeger@uwa.edu.au

induces an unfaithful buts-arc-transitive action on the normal quotient_N (defined in Sect.2). The important graphs to study are then those with no “useful” normal quo- tients, that is, those for which all nontrivial normal subgroups ofGhave at most two orbits on vertices. A transitive permutation group for which all nontrivial normal sub- groups are transitive is called quasiprimitive, while if the group is not quasiprimitive and all nontrivial normal subgroups have at most two orbits we call it biquasiprimi- tive. Thus the basic graphs to study are those which are(G, s)-arc transitive andGis either quasiprimitive or biquasiprimitive on vertices.

Now suppose that our graphwere bipartite. Then the even subgroupG⁺ (the subgroup generated by the vertex stabilisersGvfor allv∈V ) has index 2 inGand is transitive on each of the two bipartite halves of(see, for example, [7, Proposi- tion 1]). SinceG⁺ is vertex-intransitive,G is not vertex-quasiprimitive and so the basic bipartite graphs are those whereGis biquasiprimitive on vertices. The actions of such groups were investigated in [11,12]. However, whenGis biquasiprimitive it may still be possible to find a meaningful quotient of the graph. The subgroupG⁺is what is called locally transitive ons-arcs (see Sect.2for a precise definition and [8]

for an analysis of such graphs). IfG⁺is not quasiprimitive on each bipartite half (note the two actions ofG⁺ are equivalent) then we can form aG⁺-normal quotient and obtain a new (smaller) locallys-arc-transitive graph. The existence of a 2-arc transi- tive graph with such a group has been regarded as ‘problematic’ (see [11, Sect. 4]).

The main result of this paper is that there do indeed exist(G,2)-arc transitive graphs such thatGis biquasiprimitive butG⁺is not quasiprimitive on each bipartite half.

Theorem 1.1 There exist infinitely many connected bipartite (G,2)-arc transitive graphsof valency 3, whereG≤^Aut(), such thatGis biquasiprimitive on vertices butG⁺is not quasiprimitive on either bipartite half.

Such permutation groupsG were described in detail in [11, Theorem 1.1(c)(i)]

(see Corollary9.8) and this theorem gives the first examples of 2-arc-transitive graphs admitting such automorphism groups. (Our graphs are actually 3-arc transitive, but only(G,2)-arc-transitive.) We also provide an infinite family of(G,1)-arc-transitive graphs whereGis biquasiprimitive on vertices butG⁺is not quasiprimitive on each orbit (Construction3.1). The full automorphism groupAof such a graph is 2-arc- transitive butA⁺is quasiprimitive on each bipartite half.

Graphs which ares-arc transitive are alsos-distance transitive, provided their di- ameter is at leasts. Such graphs were studied in [4] where(G, s)-distance transitive bipartite graphs withGbiquasiprimitive on vertices, butG⁺not quasiprimitive on each bipartite half, were referred to asG-basic but notG⁺-basic (see [4, Proposi- tion 6.3]). Our infinite family of graphs shows that connected 2-distance transitive graphs with such an automorphism group do indeed exist and so this answers Ques- tion 6.4 of [4] in the affirmative fors=2.

We prove Theorem1.1by constructing and analysing a new infinite family of finite bipartite(G,2)-arc transitive graphs(f, α)of valency 3, wheref is a posi- tive integer andαlies in the Galois fieldGF(2^f), see Construction6.1. The group G≤^Aut((f, α))depends only onf, has order 2^2f+1(2^2f−1)², and is biquasiprim- itive on vertices, whileG⁺is not quasiprimitive on either bipartite half. Indeed we

haveN (of order 2^f(2^2f −1)) normal inG⁺and intransitive on each bipartite half (Proposition9.5). These graphs are quite large, indeed their number of vertices is 2^2f(2^2f −1)²/3 (Proposition6.3). Infinitely many of them are connected (Propo- sition8.5). The number of pairwise non-isomorphic connected graphs produced by Construction6.1grows exponentially withf (Proposition8.5); and each connected graph has relatively large girth (at least 10, Proposition9.2) and diameter (at least 6f −3, Proposition6.3).

Note thatGis not the full automorphism group of(f, α). Moreover, overgroups of biquasiprimitive and quasiprimitive groups are not necessarily biquasiprimitive or quasiprimitive respectively. Indeed we have the following:

Theorem 1.2 For each connected graph=(f, α)defined in Construction6.1, with automorphism groupA=^Aut()given in Proposition 8.1,Gis an index two subgroup ofA,is(A,3)-arc-transitive,Ais not biquasiprimitive on vertices and A⁺is quasiprimitive on each bipartite half.

We do not know if there are examples whereGis the full automorphism group.

Question 1.3 Is there a(G,2)-arc transitive graphsuch that G=^Aut()is bi- quasiprimitive on vertices butG⁺is not quasiprimitive on each bipartite half?

2 Preliminary graph definitions

We consider simple, undirected graphs , with vertex-set V and edge-set E.

A graph is called cubic if it is regular of valency 3. For a positive integers, ans- arc of a graph is an(s+1)-tuple(v0, v1, . . . , vs)of vertices such thatvi is adjacent tovi−1for 1≤i≤sandvj−1=vj+1for 1≤j ≤s−1. The distance between two verticesv1 andv2, denoted by^d(v1, v2), is the minimal numbers such that there exists ans-arc betweenv₁andv₂. For a connected graph, we define the diameter of, denoteddiam(), as the maximum distance between two vertices of.

We denote a complete graph onnvertices byKnand a complete bipartite graph with bipartite halves of sizesnandmbyKn,m. The disjoint union ofmcopies of is denoted bym.

Letbe a graph,G≤^Aut(), andNG. The (normal) quotient graph_N is the graph with vertex-set the set ofN-orbits, such that twoN-orbitsB₁andB₂are adjacent inN if and only if there existv∈B1andw∈B2with{v, w} ∈E.

Tables1and2describe some propertiesP that hold for the G-action on a con- nected graph, whereG≤^Aut()and we require thatGbe transitive on each set in some collectionP()of sets. For the local variant we require that for each vertex vof , the stabiliserG_vbe transitive on each set in a related collectionP(, v)of sets. These concepts are sometimes used without reference to a particular groupG, especially whenG=^Aut().

Next we describe coset graphs, which will be used to describe our family of graphs, and some of their properties.

Table 1 Properties forG-action on a connected graph

Property P()= {i|1≤i≤s},s= ∅

(G, s)-arc transitivity iis the set ofi-arcs of G-arc transitivity s=1 and₁is as in previous line (G, s)-distance transitivity iis{(v, w)∈V ×V |^d(v, w)=i}

G-distance transitivity s=^diam()and_iis as in previous line

Table 2 Local properties forG-action on a connected graph

Local property P(, v)= {_i(v)|1≤i≤s},s(v)= ∅for somev

local(G, s)-arc transitivity _i(v)is the set ofi-arcs ofwith initial vertexv localG-arc transitivity s=1 and₁(v)is as in previous line

local(G, s)-distance transitivity i(v)isi(v):= {w∈V |^d(v, w)=i} localG-distance transitivity s=^diam()and_i(v)is as in previous line

Definition 2.1 Given a group G, a subgroupH and an elementg∈G such that H gH =H g⁻¹H, the coset graph Cos(G, H, H gH ) is the graph with vertices the right cosets of H in G, with H g₁ and H g₂ forming an edge if and only if g2g⁻₁¹∈H gH.

Note that a coset graph is indeed undirected since g2g₁⁻¹∈H gH if and only if g1g⁻₂¹∈H g⁻¹H.

Lemma 2.2 Let=^Cos(G, H, H gH ). Then the following facts hold.

(a) has|G:H|vertices and is regular with valency|H:H^g∩H|.

(b) The group G acts by right multiplication on the coset graph with kernel

x∈GH^x, andGis arc-transitive.

(c) is connected if and only ifH, g =G.

(d) If H, g ≤ K < G, then = m where m = |G : K| and = Cos(K, H, H gH ).

(e) has |G : H, g| connected components, each isomorphic to Cos(H, g, H, H gH ).

(f) Forη∈NAutG(H ), the mapη¯:H x →H x^ηis a permutation ofV and induces an isomorphism fromtoCos(G, H, H g^ηH ).

Proof Statements (a) to (c) can be found in [10].

Assume H, g ≤K < G. By Theorem 4(i, iii) of [10], there is no edge of between vertices (that is,H-cosets) lying in distinctK-cosets. On the other hand, by the last paragraph of the proof of that same theorem, for allK-cosetsKx, the graph induced on theH-cosets contained inKx is isomorphic to=^Cos(K, H, H gH ).

Hence (d) holds. Statement (e) follows from (d) (takingK= H, g) and (c).

Letη∈NAutG(H ) and=^Cos(G, H, H g^ηH ). Then η mapsH-cosets toH- cosets and so induces the permutationη¯:V →V :H x →H x^η of V =V .

Let{H x, H y}be an edge of, that is,yx⁻¹∈H gH. Nowy^η(x^η)⁻¹=(yx⁻¹)^η∈ (H gH )^η. SinceηnormalisesH, we have(H gH )^η=H g^ηH, and so{H x^η, H y^η} is an edge of. Conversely, let{H x^η, H y^η}be an edge of, so thaty^η(x^η)⁻¹= (yx⁻¹)^η ∈ H g^ηH. Then yx⁻¹ ∈ (H g^ηH )^η−1, and since η normalises H, (H g^ηH )^η−1=H gH. Thereforeη¯ sends the edge-set ofto the edge-set of and

(f) holds.

3 1-arc-transitive examples

In this section, we construct an infinite family ofG-arc-transitive graphs such thatG is biquasiprimitive on vertices butG⁺is not quasiprimitive on each bipartite half.

Construction 3.1 LetH=Zp×Zp×Z2wherep≡1 (mod 3)is a prime. Leta be an element of multiplicative order 3 inZp. We define a graphwith vertex-setH and edges of the form

(x, y,0), (x+1, y+1,1) , (x, y,0),

x+a, y+a²,1 , (x, y,0),

x+a², y+a,1 .

This yields an undirected bipartite graph with bipartite halves1= {(x, y,0)|x, y∈ Zp}and2= {(x, y,1)|x, y∈Zp}.

Some automorphisms ofare:

• t_u,v : (x, y, ) → (x +u, y +v, ) ∈^Aut(), we denote {t_u,v|u, v∈ Zp} by N∼=Z²_p;

• τ:(x, y, ) →(ax, a²y, )∈^Aut();

• σ:(x, y, ) →(y, x, )∈^Aut();

• ν:(x, y, ) →(−x,−y,1−)∈^Aut().

We easily see from this construction that is cubic with the neighbours of the vertex(x, y, )being(x+(−1), y+(−1),1),(x+(−1)a, y+(−1)a²,1)and (x+(−1)a², y+(−1)a,1)}.

Proposition 3.2 LetG=Nτ, σ ν ∼=Z²pS3. ThenGis biquasiprimitive onV butG⁺is not quasiprimitive on each bipartite half andis(G,1)-arc transitive but not(G,2)-arc transitive. The full automorphism group ofisA=Nτ, σ, ν ∼= Z²_p(S3×Z2). Then is(A,2)-arc transitive,Ais biquasiprimitive onV and A⁺is quasiprimitive on the bipartite halves.

Proof The groupNclearly acts transitively on each bipartite half andσ νswitches₁ and2, soGis transitive onV . Moreover, since no nontrivial element ofτ, σ ν centralisesN: and sinceτ, σ νleaves invariant no subgroup ofNof orderp, it fol- lows thatNis the unique minimal normal subgroup ofGand soGis biquasiprimitive on vertices. NowG⁺=Nτhas{t_u,0|u∈Zp} ∼=Zpas a normal subgroup that is

intransitive on₁and₂. ThusG⁺is not quasiprimitive on each bipartite half. Fi- nally,G_(0,0,0)= τ, which acts regularly on the set of three neighbours of(0,0,0), and sois(G,1)-arc transitive but not(G,2)-arc transitive.

LetA=Nτ, σ, ν. ThenN is also the unique minimal normal subgroup ofA and ofA⁺=Nτ, σ. ThusAis biquasiprimitive on vertices andA⁺is quasiprim- itive on each bipartite half. Moreover,A_(0,0,0)= τ, σ ∼=S₃acts 2-transitively on the set of three neighbours of(0,0,0)and sois(A,2)-arc transitive.

LetXbe the full automorphism group of. SinceAis vertex-transitive, we have X=AXα(whereα∈V ) and so|Xα|divides 48 [14,15]. Since|Aα| =6, it follows that|X:A|divides 8. Consider the action ofX on the set of right cosets ofA. IfA is core-free inX,it follows thatX≤S₈, contradicting p² dividing|A| andp≥7.

ThusAcontains a normal subgroupMofX. SinceN is the unique minimal normal subgroup ofA,it follows thatN≤M. However,Nis the unique Sylowp-subgroup of A and hence of M, and so N X. HenceX has a normal subgroup that acts regularly on each bipartite half and so, by [9, Lemma 2.4], X_α acts faithfully on

(α). ThusX_α=A_α=S₃and henceX=A.

4 Finite fields

This section contains facts about finite fields that we need later. We denote a field of orderq byGF(q).

Definition 4.1 Letx be an element of a fieldF. The subfield generated byx is the unique smallest subfield containingx. The elementx is called a generator ofF if the subfield generated byxisF, in other words, ifx is not contained in any proper subfield ofF.

Lemma 4.2 Letf be an integer and letα∈^GF(2^f). The subfield generated byαis GF(2^e)if and only if the order ofαdivides 2^e−1 but does not divide 2^s−1 for any proper divisorsofe. In particular,αis a generator ofGF(2^f)if and only if the order ofαdoes not divide 2^e−1 for any proper divisoreoff.

Proof Since the multiplicative group ofGF(2^f)is cyclic of order 2^f −1, it follows that the multiplicative group of the subfieldGF(2^e)of GF(2^f)is precisely the sub- group of order 2^e−1, withedividing f. This subgroup is unique, since there is a unique subgroup of each order in a cyclic group. Thus the order ofαdivides 2^e−1

if and only ifα∈^GF(2^e). The result follows.

Lemma 4.3 Letf be an integer,f ≥2, and letαbe a generator of^GF(2^f). Then (a) α²ⁱ=α+1 for all positive integersi < f except possiblyi=f/2 (withf even),

and

(b) α²ⁱ=αfor all positive integersi < f.

Proof Supposeα²ⁱ =α+1 for some integeri < f. Then since GF(2^f)has char- acteristic 2, we have α²²ⁱ =(α²ⁱ)²ⁱ =(α+1)²ⁱ =α²ⁱ +1=α, so α²²ⁱ⁻¹=1.

Since 0=α∈^GF(2^f), we also have thatα^2f−1=1. Hence the order ofαdivides gcd(2²ⁱ−1,2^f −1)=2^{gcd(2i,f )}−1. Since gcd(2i, f )dividesf andαis a genera- tor, Lemma4.2implies that gcd(2i, f )=f, that is,f divides 2i. Sincef > i, this implies thatf is even andi=f/2. This proves (a).

Supposeα²ⁱ =α for some positive integer i < f. Then α²ⁱ⁻¹=1. Hence the order ofαdivides gcd(2ⁱ−1,2^f−1)=2^{gcd(i,f )}−1. Since gcd(i, f )is a divisor of f andαis a generator, Lemma4.2implies that gcd(i, f )=f, that is,f dividesi,

contradictingf > i. This proves (b).

Lemma 4.4 Letf be an integer,f ≥3. Then the number of generators ofGF(2^f)is strictly greater than 2^f−1.

Proof Forf =3, all elements ofGF(2³)\ {0,1}are generators, hence there are 6 generators and the claim holds. Assumef ≥4. Letf =_k

i=1p^e_iⁱ, where thep_i are distinct primes and eachei ≥1. Letfi=f/pi. Then all elements which are not gen- erators are in one of the subfieldsGF(2^fi). Hence the number of generators is 2^f −

|_k

i=1GF(2^fi)|. We have|_k

i=1GF(2^fi)| ≤1+^k_i=1(2^fi−1)since 0 is in all fields.

Sincef_i≤f/2 for alli, we have|_k

i=1GF(2^fi)| ≤1+k(2^f/2−1)≤k2^f/2. Since f≥_k

i=1pi≥2^k, we havek≤log₂(f ), and so|_k

i=1GF(2^fi)| ≤log₂(f )2^f/2. It is easy to check that, forf ≥4, log₂(f )≤2^f/2−1, and so log₂(f )2^f/2≤2^f−1. We can now conclude that the number of generators is at least 2^f −2^f−1=2^f−1.

Suppose we get equality. Then we have equality in all our inequalities. In particular 1+k(2^f/2−1)=k2^f/2, and sok=1, andk=log₂(f ), sof =2^k. Thusf =2, a contradiction. Therefore, the number of generators is greater than 2^f−1. Lemma 4.5 Letbe an integer,≥2. Then the number of generators of^GF(2²) which do not satisfy the equationx²=x+1 is strictly greater than 2(2⁻¹−1).

Proof By Lemma4.4,GF(2²)contains more than 2²⁻¹generators. Since the equa- tion x²=x+1 has degree 2, it has at most 2 solutions. Hence the number of generators not satisfying the equation is greater than 2²⁻¹−2=2(2⁻¹−1).

5 The groupPSL(2,2^f)

The elements of a group ^PSL(2, q) may be viewed as permutations of X :=

GF(q)∪ {∞}. More precisely,ta,b,c,dis the element t_a,b,c,d: x →ax+b

cx+d for allx∈X, (1)

wherea, b, c, d∈^GF(q)are such thatad−bc is a nonzero square of GF(q). We adopt the convention that∞is mapped byt_a,b,c,d ontoac⁻¹and that an element of GF(q)divided by 0 is∞. Forq=2^f, all nonzero elements ofGF(q)are squares, and the automorphism group ofPSL(2, q)isPL(2, q)= ^PSL(2, q), τ, where

τ:t_a,b,c,d →t_a2,b²,c²,d² for eacht_a,b,c,d∈^PSL(2, q). (2)

In this paper, we will takeT =^PSL(2,2^f)for somef ≥1. For each subfield GF(2^e)ofGF(2^f), we identifyPSL(2,2^e)with the subgroup ofT of thoset_a,b,c,d with all ofa, b, c, d∈^GF(2^e). In our construction, we will use the following notation for elements ofH=^PSL(2,2)≤T:

a=t_1,1,1,0: x →1+1

x, b=t_1,1,0,1: x →x+1. (3) Note thatahas order 3,bhas order 2, andH= ab ∼=S₃. Forα∈^GF(2^f), we will also need the following elements ofT:

u_α=t1,α,0,1: x →x+α, c_α=a^uα=t_α+1,α2+α+1,1,α. (4) LetP be the Sylow 2-subgroup ofT containing the involutionb=u₁, that is,P = {u_α|α∈^GF(2^f)}. Then NT(P )∼=^AGL(1,2^f)is the set of permutationst_r,s,0,1:x → rx+swithr=0.

Lemma 5.1 Let α∈^GF(2^f). Using the notation introduced above, the following facts hold.

(a) CT(b)=P. In particular,u_αb=bu_α=u_α+1and CH(b)= b.

(b) Forα=0, the element z_α :=t_α−1,0,0,1∈NT(P ). Moreover u_α =b^zα and the order ofz_α is equal to the multiplicative order ofα.

(c) c_α^τi=c_α⁻¹if and only ifα²ⁱ=α+1.

(d) NT(H )=H.

(e) If the subfield generated byαisGF(2^e), thenH, u_α =^PSL(2,2^e).

Proof (a) The centraliser ofbinT is easily computed. Sinceu_α ∈P, it then com- mutes withb, andbu_α=u_α+1. Also CH(b)=CT(b)∩H= b.

(b) A calculation shows thatu^z_y^α=u_αy∈P, and soz_α∈NT(P ). Alsou_α=u^z₁^α=b^zα. Sincez_α^j=t_α−j,0,0,1the rest of the statement follows.

(c) This is a simple calculation left to the reader.

(d) LetD=NT(a). NowDis a dihedral groupD₂₍₂f±1), see [5, Sect. 260]. Since a ∼=C3 is characteristic in H ∼=S3, NT(H )≤NT(a)=D, and so NT(H )= ND(H ). Since anS3subgroup in a dihedral groupD2n,nodd, is self-normalising, we have that ND(H )=H. Thus NT(H )=H.

(e) Suppose the subfield generated by α is ^GF(2^e). If e=1, then α=0 or 1, u_α∈H andH, u_α =H=^PSL(2,2). Assume nowe≥2. Since all the subscripts of u_α =t1,α,0,1 are in ^GF(2^e), we obviously have H, u_α ≤^PSL(2,2^e). Suppose that H, u_α ≤M, whereM is a maximal subgroup ofPSL(2,2^e). Since H, u_α contains a subgroup isomorphic toS3,M cannot be isomorphic toAGL(1,2^e)(for e even, 3 divides|^AGL(1,2^e)| but no involution in AGL(1,2^e)inverts an element of order 3). Also sinceH, u_αcontains subgroups which are isomorphic toC₂²,M cannot be isomorphic toD₂₍₂^e_±1). It follows from the list of maximal subgroups of PSL(2,2^e)(see [5, Sect. 260]) thatM∼=^PSL(2,2^s)for some proper divisorsofe.

Sinceb, u_α ∈Mcommute, they lie in the same Sylow 2-subgroupS ofM, so there existsd∈M such thatb^d=u_α. Henceb^d=u_α =b^zα (by Part (b)), and sodz_α⁻¹

centralisesb. Since CT(b)=P by (a), we obtain thatd∈P z_α. Sincez_α∈NT(P ) has ordern:= |α|, it follows thatd has order divisible byn. Moreover,dmust be in NM(S)∼=^AGL(1,2^s), and so the order ofd divides 2^s−1. Thusndivides 2^s−1, a contradiction to Lemma4.2. Thus,H, u_α =^PSL(2,2^e).

6 The family of graphs

Letf be a positive integer, and letT,H,a,b,α,z_α(forα=0),u_α, andc_α be as in Sect.5.

Construction 6.1 Let G=T²π, where π ∈^Aut(T²) is such that(x, y)^π = (y, x), for all elements(x, y)∈T². LetL= (a, a), (b, b)< T², and

gα=(uα, buα)π=(uα, uαb)π=(t1,α,0,1, t1,α+1,0,1)π. (5) By Lemma6.2(c) below,g_α⁻¹=g_α(b, b). ThusLg_α⁻¹L=Lg_α(b, b)L=Lg_αL. De- fine=(f, α)=^Cos(G, L, LgαL).

We shall need information about the following subgroups:

Xα= L, gα, Nα= L, c⁻_α¹, cα

. (6)

Lemma 6.2 The following facts hold.

(a) |G| =2^2f+1(2^2f −1)².

(b) (a, a)^gα=(c⁻_α¹, c_α), wherec_αis as in (4) and has order 3. ThusN_α≤X_α. (c) g⁻_α¹=g_α(b, b)and(b, b)^gα=(b, b).

(d) Forf ≥2 andα a generator ofGF(2^f), eitherNα =T² orNα = {(t, t^ν)|t∈ T} ∼=T for someν∈^Aut(T ).

Proof (a) follows from the fact that|G| =2|T|².

(b) We have(a, a)^gα =(a^uα, (a^b)^uα)^π =(cα, c⁻_α¹)^π=(c⁻_α¹, cα), by (4), and hence N_α≤X_α. Sincec_αis conjugate toa, it has order 3.

(c) We have g²_α(b, b)=(u_α, bu_α)π(u_α, bu_α)π(b, b)=(u_α, bu_α)(bu_α, u_α)(b, b)= (1,1) since uαb =buα by Lemma 5.1(a). Thus g_α⁻¹=gα(b, b). We also have (b, b)^gα=(b^uα, b^uαb)^π=(b, b)^π=(b, b), using Lemma5.1(a) for the second equal- ity.

(d) The projections ofN_α onto each of the two coordinates are equal toa, b, c_α. Sinceuαb=buα, the subgroupa, b, cαofT is normalised by each ofa, banduα. Hencea, b, c_αa, b, u_α, anda, b, u_α =T by Lemma5.1(e). Thusa, b, c_α = T sinceT is simple, and soN_α=T²orN_α∼=T. In the latter case,N_α is a diagonal subgroup ofT²and henceNα= {(t, t^ν)|t∈T} ∼=T for someν∈^Aut(T ).

We first describe some general properties of the graphs(f, α).

Proposition 6.3 Letf ≥1 be an integer andαbe an element ofGF(2^f). Let= (f, α),G,T,L,π be as in Construction6.1. Thenis bipartite, cubic, and, if is connected, then it has diameter at least 6f −3. Moreover,G⁺=T²,G≤^Aut() and|V | =2^2f(2^2f −1)²/3.

Proof By Lemma6.2(b),(a, a)^gα=(c⁻_α¹, c_α), which is not inLsincec_α=c⁻_α¹, and, by Lemma6.2(c),(b, b)^gα=(b, b). Thus the intersectionL^gα∩L= (b, b) ∼=C2, and so the graphhas valency|L:L^gα∩L| =3 (hence is cubic) by Lemma2.2(a).

Moreover,T²has two orbits on the cosets ofL, and sinceT²∩LgαL= ∅, no vertices in the same orbit are adjacent. Henceis bipartite. SinceT²is an index 2 subgroup ofGand its orbits are the two bipartite halves, the even subgroupG⁺is preciselyT². The number of vertices ofis|G|/|L| =2^2f(2^2f −1)²/3, with each bipartite half of size 2^2f−1(2^2f −1)²/3.

Supposeis connected and letd=^diam(). We have|₁(L)| =3 and|_i(L)|is at most 2|_i−1(L)|for 2≤i≤d. Hence the number of vertices ofis at most 1+ 3+3.2+ · · · +3.2^d−1=1+3(2^d−1). Therefore 2^2f(2^2f−1)²/3≤1+3(2^d−1), or equivalently, 2^2f(2^2f −1)²/9+2/3≤2^d, which implies 2^2f(2^2f −1)²/9<2^d. Thus(2^2f−1)/3<2^d2−f. Now for allf ≥1, we have(2^2f−1)/3≥2^2f/4=2^2f−2, and so 2^2f−2<2^d2−f. Therefore, 2f −2<^d₂−f andd >6f−4. Since

x∈GL^x is trivial, it follows from Lemma2.2(b) thatGacts faithfully on, and henceG≤

Aut().

Note that the bound on the diameter is not tight. For example, for f =3 a MAGMA [2] computation shows that(3, α)has diameter 21 forαa generator of GF(8)(we will see in Corollary8.6that the graph is connected in this case).

7 Equality and connectivity

We first have a lemma determining when graphs obtained by Construction6.1have the same edge-set.

Proposition 7.1 Letf≥1. Letα, βbe elements ofGF(2^f). Then(f, α)=(f, β) if and only ifβ∈ {α, α+1}.

Proof Suppose that (f, α)=(f, β). Then the double cosets Lg_αL and Lg_βL coincide, and so gβ ∈LgαL. Since π centralises L, this implies, using (5), that (uβ, buβ)=(h1, h1)(uα, buα)(h2, h2)for someh1, h2∈H. Thush1buαh2=buβ= bh1uαh2, and soh1commutes withb. SincebcentralisesP by Lemma5.1(a) and uα, uβ ∈P, we also haveh1uαbh2=uβb=h1uαh2b, and so h2 also commutes withb. Henceh1, h2∈CH(b)= bby Lemma5.1(a). Ifh1=h2, thenα=β, and ifh₂=h₁bthenβ=α+1.

Conversely, ifβ=α+1, theng_β=(u_β, u_βb)π=(u_αb, u_α)π=g_α(b, b), and so

Lg_αL=Lg_βL. Thus(f, α)=(f, β).

Forf =1 Construction6.1yields only one graph.

Lemma 7.2 (1,0)=(1,1)=2K_3,3.

Proof Here T =H, and by Proposition 7.1, (1,0)=(1,1) so we may as- sume α=0. Thus u_α =1 and g_α =(1, b)π. It can be computed that L, g_α = {(x, y)|x⁻¹y∈ a} ∪ {(x, yb)π|x⁻¹y∈ a}has index 2 inG. Therefore, by Lemma 2.2(e),(1,0)has 2 connected components. Each must be bipartite and have valency

3 by Proposition6.3, hence the conclusion.

The next two general results allow us to determine the connected components of (f, α).

Lemma 7.3 Letαbe an element ofGF(2^f)and letGF(2^e)be the subfield generated byα. Then(f, α)∼=m(e, α), wherem= |T :^PSL(2,2^e)|².

Proof LetK=^PSL(2,2^e)²π viewed as a subgroup of G. Then g_α ∈K and L≤K, and soL, g_α ≤K. By Lemma2.2(d),(f, α)=mwherem= |G:K| and=^Cos(K, L, Lg_αL). Finally, m= |G:K| =2|T|²/(2|^PSL(2,2^e)|²)= |T :

PSL(2,2^e)|².

Proposition 7.4 Letf ≥2 andα∈^GF(2^f)be a generator.

(a) Iff is odd, or iff is even andα^2(f/2)=α+1, then(f, α)is connected.

(b) Iffis even andα^2(f/2)=α+1, then(f, α)has|T|connected components, each containing |T|/3 vertices and isomorphic to ^Cos(T , ν, H, H u_ανH ) where H=^PSL(2,2)andν=τ^(f/2).

Proof We setXα= L, gαandNα= L, (c_α⁻¹, cα)as in (6). By Lemma2.2(e), the number of connected components of(f, α)is|G:X_α|and all connected compo- nents are isomorphic toCos(X_α, L, Lg_αL).

We haveα /∈ {0,1}, sinceαis a generator andf =1.

By Lemma6.2(b), N_α ≤X_α, and by Lemma6.2(d), either N_α =T² or N_α = {(t, t^ν)|t ∈T} for some ν∈^Aut(T ). In the latter case, since Nα contains (a, a), (b, b)and(c⁻_α¹, cα),ν must be in CAut(T )(a, b)and must satisfyc^ν_α=c_α⁻¹. Since a, b =^PSL(2,2), we have CAut(T )(a, b)=CAut(T )(PSL(2,2))=^Aut(GF(2^f))= τ ∼=C_f, whereτ is the Frobenius automorphism described in (2).

Assumef is odd, orf is even andα^2(f/2)=α+1. Then by Lemma4.3(a),α²ⁱ= α+1 for alli < f, and so by Lemma5.1(c),c_α^τi=c_α⁻¹for alli < f. Hence there is noν∈CAut(T )(a, b)satisfyingc^ν_α=c⁻_α¹. ThusN_α =T², and soX_α=Gsince gα∈/T². Thus(f, α)is connected and (a) holds.

Now assumef is even andα²ⁱ=α+1, wherei=f/2. Letν:=τⁱ. By Lemma 5.1(c), ν∈CAut(T )(a, b)and satisfiesc^ν_α=c⁻_α¹, and soNα= {(t, t^ν)|t ∈T} ∼=T. Noticeνis an involution. We haveN_α≤X_α, and soN_α, g_α ≤ X_α, g_α =X_α. On the other hand,X_α= (a, a), (b, b), g_α ≤ (a, a), (b, b), (c_α⁻¹, c_α), g_α = N_α, g_α. Thus X_α = N_α, g_α. Notice that u^ν_α = t

1,α²ⁱ,0,1= u_α+1 =u_αb, and so g_α = (u_α, u^ν_α)π. Therefore,N_α, g_α = N_α, π =N_απ. Hence,|X_α| =2|N_α| =2|T|.

Moreover,X_α= {(t, t^ν)π|t∈T , ∈ {0,1}}. Also the number of connected compo- nents is|G:X_α| = |T|by Lemma2.2(e).

We now prove thatX_α is isomorphic toT , ν. We define φ:Xα→ T , ν :(t, t^ν)π →t ν.

We first show thatφis a homomorphism, that is, thatφ ((t1, t₁^ν)π¹(t2, t₂^ν)π²)= φ ((t1, t₁^ν)π¹)φ ((t2, t₂^ν)π²). This clearly holds for1=0. We now prove the case 1=1.

φ t₁, t₁^ν

π t₂, t₂^ν

π²

=φ t₁, t₁^ν

t₂^ν, t₂ π π²

=φ

t1t₂^ν, t₁^νt2

π¹⁻²

=t₁t₂^νν¹⁻²

=t₁νt₂νν¹⁻²

=(t₁ν) t₂ν²

=φ t₁, t₁^ν

π φ

t₂, t₂^ν π²

.

Thusφis a homomorphism. Clearly,Kerφ=1, and|X_α| = |T , ν| =2|T|, and soφ is a bijection. Therefore,φis an isomorphism.

Notice thatφ (L)= a, b =Handφ (gα)=uαν.

By Lemma 2.2(e), each connected component of (f, α) is isomorphic to Cos(X_α, L, Lg_αL), and φ induces a graph isomorphism ^Cos(X_α, L, Lg_αL)∼= Cos(T , ν, H, H u_ανH ). Thus (b) holds.

Note that the proof of Proposition7.4uses the fact thatT is simple through Lemma 6.2(d) and hence requiresf ≥2.

Putting together Lemma7.3and Proposition7.4, we get the following corollary.

Corollary 7.5 Letf≥2 and letGF(2^e)be the subfield generated byα.

(a) Ifeis odd, or ifeis even andα^2(e/2) =α+1, then(f, α)=m(e, α), where m= |T :^PSL(2,2^e)|²and(e, α)is connected.

(b) Ifeis even andα^2(e/2) =α+1, then(f, α)has|^PSL(2,2^e)|⁻¹|^PSL(2,2^f)|² connected components, each isomorphic to Cos(^PSL(2,2^e), ν, H, H uανH ), whereH=^PSL(2,2)andν=τ^(e/2).

We can now deal with the casef =2. Take^GF(4)= {a+bi|a, b∈^GF(2), i²= i+1}. By Proposition7.1, Construction 6.1yields two graphs forf =2, namely (2,0)and(2, i).

Corollary 7.6 The two graphs obtained by Construction6.1forf =2 are not con- nected. More precisely,

(a) (2,0)∼=200K_3,3, and

(b) (2, i)∼=60DwhereDis the incidence graph of the Desargues configuration, called the Desargues graph (it is a double cover of the Petersen graph).

Proof Consider first α= 0. By Lemma 7.3, (2,0)∼= m(1,0), where m=

|^PSL(2,2²):^PSL(2,2¹)|²=100. Part (a) follows from Proposition7.2.

Now assumeα=i. Then α^2(f/2) =i²=i+1=α+1, so part (b) of Propo- sition 7.4 holds. Here u_α =t_1,i,0,1 and ν =τ. Thus (2, i) has |^PSL(2,2²)| = 60 connected components, each containing 60/3=20 vertices and isomorphic to Cos(PL(2,4), H, H uατ H )whereH=^PSL(2,2). There are only two arc-transitive cubic graphs on 20 vertices, the Desargues graph and the dodecahedron (see [1, p. 148]). Since(2, i)is bipartite by Proposition6.3, its connected components can- not be dodecahedrons, hence they are Desargues graphs. The Desargues graph has vertices the points and lines of the Desargues configuration, with two vertices adja- cent if they form a flag (incident point-line pair) of the configuration. It is a double

cover of the Petersen graph.

8 Automorphism groups and isomorphisms for connected(f, α)

The remainder of this paper is concerned mainly with the connected graphs(f, α) given by Construction6.1, that is, we may assume from now on thatαis a gener- ator and, iff is even, thenα^2(f/2)=α+1 (see Corollary7.5). By Lemma7.2and Corollary7.6, we may assume thatf≥3.

In this section, we determine the full automorphism groupAof=(f, α)and the normaliser ofAinSym(V ). This will then enable us to determine a lower bound on the number of non-isomorphic such graphs, for a givenf.

Proposition 8.1 Letf ≥3 be an integer andα∈^GF(2^f). Let=(f, α),G,T, L,πbe as in Construction6.1withconnected. The full automorphism group of isA=G× σ, whereσ is given by(Lx)^σ =Lπ x for allx∈G. In particular,A does not depend on the choice ofαandis(A,3)-arc transitive but not(A,4)-arc- transitive. Moreover, the stabiliser inAof the vertexLisL× π σ ∼=D12.

Proof LetAbe the full automorphism group of. By Proposition6.3,G≤A. De- fine the mapσ onV by(Lx)^σ =Lπ x for allx∈G. This is a well defined bijec- tion, sinceπcentralisesL. Consider an edge{Lg₁, Lg₂}, that is,g₂g⁻₁¹∈Lg_αL. Its image underσ is{Lπg1, Lπg2}. We haveπg2(πg1)⁻¹=πg2g⁻₁¹π ∈π Lg_αLπ= Lπg_απ L. Recall thatg_α=(u_α, u_αb)π andu_αb=bu_α, so πg_απ=(u_αb, u_α)π= (b, b)g_α. ThusLπg_απ L=Lg_αL, so{Lg1, Lg2}^σ is an edge, andσ ∈A. We now show thatσcentralisesG. Indeed, leth∈GandLx∈V , then(Lx)^hσ =(Lxh)^σ= Lπ xh=(Lπ x)^h=(Lx)^{σ h}. Henceσ h=hσ, andσ ∈CA(G). Since Z(G)=1, we haveσ /∈G. Alsoσ²=1. Therefore,R:=G× σ ≤A. The stabiliser ofL∈V in RisR_L=L× π σ ∼=S₃×C₂∼=D₁₂.

By Lemma2.2(b),is(G,1)-arc transitive, and so is(R,1)-arc transitive. Tutte [14,15] proved that the automorphism group of an arc-transitive finite graph with valency 3 acts regularly ons-arcs for somes≤5, and the stabiliser of a vertex has