On the Geodesic transitivity of Finite Graphs

Jin WeiTan Li

(1.School of Mathematics and Statistics,Central South University,Changsha410075,China;2.School of Statistics,Jiangxi University of Finance and Economics,Nanchang330013,China)

Abstract The symmetry problem for finite graphs has been extensively investigated over the past few decades.This article is devoted to giving an introduction in one particular family of symmetric graphs,namely(locally)s geodesic transitive graphs.Recently,substantial progress has been made on the study of this family of graphs,many open problems have been solved,and many new research problems have arisen.The methods used in this area range from deep group theory,including the finite simple group classification,through to combinatorial techniques.

Key words Cayley graph s geodesic transitive graph Permutation group

1 Introduction

The study of symmetry in graphs is one of the main themes in algebraic graph theory.By definition,a graph is symmetric or arc transitive if its automorphism group is transitive on the set of ordered pairs of adjacent vertices.This study goes back to the classical work of Tutte[40,41]in1947and1959showing that there are no6 arc transitive graphs of valency3.Since then,symmetry properties of graphs have attracted a great deal of attention and many important results have been proved.

The central object of this article is one particular family of symmetric graphs,namely the family of(locally)sgeodesic transitive graphs.In differential geometry and physics,and indeed in common usage,a geodesic is a shortest line between two points on a curved or plane surface.In a discrete setting(for example a graph),there is a discrete notion of distance that allows us to define geodesics analogously.We define a geodesic from a vertexuto a vertexvof a graphΓas any shortest path fromutov,where we measure distance by the number of edges.We call a geodesic ansgeodesic if the distance betweenuandviss.In the infinite setting geodesics play an important role,for example,in the classification of infinite distance transitive graphs[26],and in studying locally finite graphs,see for example,[39].In this article,we are interested in transitivity properties on geodesics in finite graphs.We say that a graphΓissgeodesic transitive if,it contains ansgeodesic,and for eachi≤s,Aut(Γ)is transitive on the set ofigeodesics ofΓ.Moreover,Γis said to be geodesic transitive if it issgeodesic transitive for all possibles.Many well known finite graphs have this transitivity property.For instance,both the complete graph Knand the complete bipartite graph Kn,nare geodesic transitive for anyn≥1.These two graphs have diameter at most2.The Johnson graphs,Hamming graphs and Odd graphs are all geodesic transitive,and these graph families have both diameter and valency unbounded.

Over the past few decades,people are also particularly interested in two other symmetry properties of graphs:including(local)sdistance transitivity and(local)sarc transitivity.These two symmetry properties of graphs have internal relationship with(local)sgeodesic transitivity of graphs.In this article,we will compare these three symmetry properties of graphs and also review some of the literature about them.

2 Preliminaries

In this section we collect some basic notations,definitions and some preliminary results relating to abstract groups,permutation groups,graphs and geometric structures that will be used in the subsequent sections.

2.1 Finite groups and permutation groups

All groups in this article are finite groups,and the notation and terminology of group theory are standard,see for instance[32,36,37].For convenience,we recall a few frequently used concepts and results.

LetGbe a group.A subgroupHofGis called a normal subgroup ifHg=Hfor anyg∈G,and we writeH⊴G.Clearly,the identity andGitself are two normal subgroups,called trivial normal subgroups.The groupGis called a simple group if it has no non trivial normal subgroups.

An abelian group is a groupGsatisfying thatab=bafor all elementsa,bofG.The center ofGis the subgroup{g∈G|gx=xg,∀x∈G},and is denoted byZ(G).

For a finite groupG,a non trivial normal subgroup ofGis called a minimal normal subgroup if it does not contain any other proper normal subgroup ofG.The socle,soc(G),ofGis the product of all minimal normal subgroups ofG.

We use standard notations and definitions for permutation groups,which can be found in[4,10,43].

For a finite set Ω,a bijection from Ω to itself is called a permutation of Ω.The set of all permutations of Ω forms a group,under composition of mappings,called the symmetric group on Ω,denoted by Sym(Ω).Any subgroup of Sym(Ω)is called a permutation group of Ω.In particular,if the size of set Ω isn,then Sym(Ω)is denoted by Sym(n)orSnand any subgroup of Sym(n)is said to be of degreen.

LetGbe a group and Ω be a non empty set.Assume that for everya∈Ω and everyg∈Gwe have defined an element of Ω denoted byag.Then we say that this defines an action ofGon Ω if the following two conditions hold:

(1)a1=afor alla∈Ω,where1is the identity element ofG;

(2)(ag)h=aghfor alla∈Ω and allg,h∈Ω.

In other words,an action ofGon Ω is a mapping(a,x)→axfrom Ω×Gto Ω satisfying the above two conditions.The size|Ω|of Ω is called the degree of theGaction on Ω.An elementaof Ω is said to be fixed by the elementg∈Gifag=a.The elements ofGwhich fix all elements of Ω form a subgroup ofG,called the kernel of this action.If the kernel is equal to the identity subgroup ofG,then we say the action is faithful.

Suppose a groupGacts on a set Ω.For a pointa∈Ω,we denote byaG={ag|g∈G}the set of images ofaunderG,and this set is called the orbit ofaunderG.The stabilizer ofainGis the following subgroup ofG,Ga={g∈G|ag=a}.

The groupGis said to be transitive on Ω,if it has exactly one orbit,that is,aG=Ω for alla∈Ω.A transitive groupGis said to be regular on Ω,if for any elementa∈Ω,the stabilizerGa=1;Gis said to be2 transitive on Ω,ifGais transitive on Ω{a}.

LetM,Kbe groups and suppose that we have an action ofMonKwhich respects the group structure ofK;so for eachx∈Mthe mappingu →uxis an automorphism ofK.PutG:={(u,x)|u∈K,x∈M}and define a product onGby(u,x)(v,y)=(uvx−1,xy)for all(u,x),(v,y)∈G.ThenGis a group called the semidirect product ofKbyM.

2.2 Primitive groups and quasiprimitive groups

In this subsection,we present two families of permutation groups with strong transitivity properties.For notations and definitions refer to[29,30].

LetGbe a group acting transitively on a set Ω.A partition of Ω is a setB={B1,B2,...,Bn}of non empty subsets of Ω such thatBi∩Bj=∅wheneveri=jand Ω=B1∪B2∪···∪Bn.A partitionBisGinvariant if for eachg∈G,and eachBi∈B,thenBgi∈B.The partition into singletons and the partition with a single part are the trivial partitions of Ω,and all the other partitions are non trivial.Each elementBof aGinvariant partition is called a block ofG.The whole set Ω is a block and the singleton{α}withα∈Ω are blocks,and they are called trivial blocks,and others are non trivial blocks.The action ofGon Ω is said to be primitive ifGhas no non trivialGinvariant partitions;otherwise,the action is said to be imprimitive.

Assume thatGis imprimitive on Ω.Then there exists a non trivialGinvariant partition of Ω,called an imprimitive partition or a system of imprimitivity ofG.

The following result gives two basic properties of primitive groups.

Lemma2.1([10,Corollary1.5 A and Theorem1.6 A])LetGbe a group acting transitively on a setΩ with at least two points.Then the following hold.

(1)Gis primitive on Ω if and only if,the stabilizerGαis a maximal subgroup ofGfor everyα∈Ω.

(2)IfGis primitive on Ω,then every non trivial normal subgroup ofGis transitive on Ω.

Note that the converse of Lemma2.1 (2)is not true.We call a transitive permutation groupGon a setΩ quasiprimitive if all its non trivial normal subgroups are transitive.Hence every primitive permutation group is a quasiprimitive group.There exist quasiprimitive but not primitive groups,for example,each transitive permutation representation of a nonabelian simple group for which a point stabilizer is not a maximal subgroup decides a quasiprimitive group which is not primitive.

There is a remarkable classification of finite primitive permutation groups mainly due to M.O’Nan and L.Scott,called the O’Nan Scott Theorem for primitive permutation groups,see[23,34].They independently gave a classification of finite primitive groups,and proposed their result at the“Santa Cruz Conference in finite groups”in1979.The class of finite quasiprimitive permutation groups can be described in a fashion very similar to the description given by the O’Nan Scott Theorem for finite primitive permutation groups[29].There are eight types of finite quasiprimitive permutation groups,which in most cases parallel the primitive types from the O’Nan Scott Theorem,and every finite quasiprimitive permutation group belongs to exactly one of these types[30].

The first three quasiprimitive types,namely types HA,HS,and HC,are exactly the same as the corresponding primitive types,that is,all quasiprimitive permutation groups of these types are primitive.For the HS type,the quasipimitive permutation groupGhas only one minimal normal subgroup;for types HS and HC,Ghas exactly two minimal normal subgroups,and these two minimal normal subgroups are isomorphic.

The following result is the O’Nan Scott Theorem for quasiprimitive permutation groups due to Praeger,see[29].

Theorem2.1(O’Nan Scott Theorem)LetGbe a finite quasiprimitive group acting on a set Ω.ThenGis one of the types{HA,HS,HC,AS,SD,CD,TW,PA}.

2.3 Graph theory

In this subsection,we collect some basic definitions and preliminary results in graph theory and algebraic graph theory.The basic notation and definitions can be found in[2],[3]or[17].

A finite graphΓis a triple consisting of a finite vertex setV(Γ),an edge setE(Γ),and a relation that associates with each edge two vertices.If edges ofΓhave no orientation,that is,edge{u,v}is identical to the edge{v,u},thenΓis said to be undirected.An undirected graph is said to be simple if,it has at most one edge between any two distinct vertices and if{u,v}is an edge,thenu=v.In simple graphs,edges can be identified with unordered pairs of adjacent vertices.The picture in Figure1is a such graph.All graphs of this article are finite simple graphs.

LetΓbe a graph.We use Aut(Γ)to denote its automorphism group.The graphΓis said to beGvertex transitive(orGedge transitive)if the action ofG≤Aut(Γ)on the vertex setV(Γ)(or the edge setE(Γ))is transitive.In particular,ifG=Aut(Γ),thenΓis said to be vertex transitive(or edge transitive).The size ofV(Γ)is called the order ofΓ.

For a vertexu∈V(Γ),letΓ(u)be the set of vertices ofΓadjacent tou.If further,the size|Γ(u)|of Γ(u)is independent ofu,the graphΓis said to be regular,and|Γ(u)|is called the valency ofΓ.

For(not necessarily distinct)verticesuandvinV(Γ),a walk fromutovis a finite sequence of vertices(v0,v1,...,vn)such thatv0=u,vn=vand(vi,vi+1)∈E(Γ)for alliwith0≤i＜n,andnis called the length of the walk.Ifvi=vjfor0≤i＜j≤n,the walk is called a path fromutov.The smallest value fornsuch that there is a path of lengthnfromutovis called the distance fromutovand is denoteddΓ(u,v).The diameter diam(Γ)of a connected graphΓis the maximum ofdΓ(u,v)over allu,v∈V(Γ).For a positive integeri≤diam(Γ),letΓi(u)be the set of vertices ofΓwhich are at distanceifromu.In particular,Γ1(u)=Γ(u).

For a positive integern,letCndenote the cycle of lengthn,and let Kndenote the complete graph onnvertices in which every pair of distinct vertices are adjacent.For two integersm≥3,b≥2,let Km[b]denote the complete multipartite graph,whose vertex set consisting ofmparts of sizeb,with edges between all pairs of vertices from distinct parts.In particular,K3[2]is called the octahedron,see the graph in Figure1.This graph has order6,valency4and diameter2.

Figure1 Octahedron

LetΓbe a graph,andG≤Aut(Γ).SupposeB={B1,B2,...,Bn}is a partition ofV(Γ).The quotient graphΓBofΓrelative toBis defined to be the graph with vertex setBsuch that{Bi,Bj}is an edge ofΓBif and only if there existx∈Bi,y∈Bjsuch that{x,y}∈E(Γ).We say thatΓBis non trivial if1＜|B|＜|V(Γ)|.If for any two adjacent blocksBi,Bjandx∈Bi,we have|Γ(x)∩Bj|=1,then we say thatΓis a cover ofΓB.IfBisGinvariant,thenGhas an induced action onΓBas a subgroup of automorphisms.Whenever the blocks inBare theNorbits,for some non trivial normal subgroupNofG,we will writeΓB=ΓN,and call it aGnormal quotient ofΓ.Moreover,ifΓis a cover ofΓBand ΓB=ΓN,thenΓis called aGnormal cover ofΓB.The automorphism group of the graph Σ of Figure1 has a normal subgroupNof order2with orbits the antipodal pairs of vertices,one of them being{u1,u4},and that the normal quotient ΣN∼=K3.Note that Σ is not a cover of ΣN,asu1is adjacent to all the vertices of other orbits.

A clique of a graphΓis a complete subgraph and a maximal clique is a clique which is not contained in a larger clique.The clique graphC(Γ)ofΓis the graph with vertex set{all maximal cliques ofΓ},and two maximal cliques are adjacent inC(Γ)if and only if they have at least one common vertex inΓ.For example,in the graph Σ of Figure1,the subgraph[{u1,u2}]is a clique and the subgraph[{u1,u2,u3}]is a maximal clique.

For a finite groupG,and a subsetSofGsuch that1/∈SandS=S−1,the Cayley graph Cay(G,S)ofGwith respect toSis the graph with vertex setGand edge set{{g,sg}|g∈G,s∈S}.The groupR(G)={ρx|x∈G},whereρx:g →gx,is a subgroup of the automorphism group of Cay(G,S)and acts regularly on the vertex set.It follows that Cay(G,S)is vertex transitive.The graph in Figure1is isomorphic to Cay(G,S)whereG=a ∼=Z6andS={a,a2,a4,a5}.

The following is a criterion for a connected graph to be a Cayley graph.

Lemma2.2([2,Lemma16.3 ],[33])LetΓbe a connected graph andHbe a subgroup of Aut(Γ).ThenHacts regularly onV(Γ)if and only ifΓis isomorphic to a Cayley graph Cay(H,S)for some setSwhich generatesH.

Recall that for a graphΓ,thekdistance graphΓkofΓis the graph with vertex setV(Γ),such that two vertices are adjacent if and only if they are at distancekinΓ.Ifd=diam(Γ)≥2,andΓdis a disjoint union of complete graphs,thenΓis said to be an antipodal graph.Suppose thatΓis an antipodal graph of diameterd.Then we may partition its vertices into sets,such that any two distinct vertices in the same part are at distancedand two vertices in different fibres are at distance less thand.The octahedron in Figure1 is an antipodal graph with fibres of size2.Godsil,Liebler and Praeger[16]gave a complete classification of antipodal distance transitive covers of complete graphs.

2.4 Partial linear spaces

An incidence structure is a tripleS=(P,L,I)wherePis a set of points,Lis a set of lines andI⊆P×Lis the incidence relation.If(p,ℓ)∈I,then we say that the pointpand the lineℓare incident.The incidence graphof an incidence structureS=(P,L,I)is the bipartite graph with vertex setP∪Land edge set{(p,ℓ)|p∈P,ℓ∈L,(p,ℓ)∈I}.TheSline graph(Spoint graph)ofSis the graph with vertex setL(vertex setP)and two vertices are adjacent if and only if they are incident with a common point(line,respectively).We refer to theSline graph rather than simply the line graph to distinguish this notion from the line graph of a graph.Given an incidence structureS=(P,L,I),we denote the transposed incidence relation byI∗={(ℓ,p)|(p,ℓ)∈I}.The new incidence structureS∗=(L,P,I∗)is called the dual ofS.Note thatS∗∗=S,and theS∗line graph is theSpoint graph,etc.

A partial linear space is an incidence structureS=(P,L,I)such that any line is incident with at least two points,any point is incident with at least two lines,and any pair of distinct points is incident with at most one line.In particular,we say that a partial linear space has order(m,n)if each point is incident withmlines,and each line is incident withnpoints.Given a partial linear spaceS=(P,L,I),the dual incidence structureS∗=(L,P,I∗)ofSis also a partial linear space whose order is(n,m)and is called the dual partial linear space ofS.A triangle ofSis a clique of theSpoint graph of size three such that the three points are not incident with a common line.For two partial linear spacesS1=(P1,L1,I1)andS2=(P2,L2,I2),a bijectionϕ:P1→P2,L1→L2is called an isomorphism betweenS1andS2if,(p1,ℓ1)∈I1if and only if(p1,ℓ1)ϕ∈I2.In particular,ifS1=S2,thenϕis called an automorphism ofS1.

3 Finite s geodesic transitive graphs

The family ofsgeodesic transitive graphs is the central object of this article,and we give its formal definition here.Recall that a geodesic from a vertexuto a vertexvof a graphΓis any shortest path fromutov.This geodesic is called ansgeodesic if the distance betweenuandviss.

Definition3.1LetΓbe a connected graph,G≤Aut(Γ)ands≤diam(Γ).

(1)Γis said to be locally(G,s) geodesic transitive if it has ansgeodesic,and for all verticesv∈V(Γ),and for eachi=1,2,...,s,the stabilizerGvis transitive on theigeodesics starting atv.Whens=diam(Γ),Γis said to be locallyGgeodesic transitive.

(2)Γis said to be(G,s) geodesic transitive if it has ansgeodesic,and for eachi=1,2,...,s,Gis transitive on the set of alligeodesics ofΓ.Whens=diam(Γ),Γis said to beGgeodesic transitive.

Moreover,in the previous definitions,ifG=Aut(Γ),thenGis often omitted and we write simplysgeodesic transitive,etc.

It is easy to see thatΓis(G,s) geodesic transitive if and only ifΓis both locally(G,s) geodesic transitive andGvertex transitive.

Remark3.1For a graphΓandG≤Aut(Γ)if,for everyu∈V(Γ),Guis transitive onsgeodesics starting fromu,it is possible that there exists a vertexvsuch thatGvis not transitive on(s−1) geodesics starting fromv.The two graphs in Figure2are examples fors=2.Thus in the definition of local(G,s) geodesic transitivity,it is necessary to require that for everyu∈V(Γ),Guis transitive onigeodesics starting fromufor alli=1,2,...,s.

Many well known finite graphs have this transitivity property.For instance,both the complete graph Knand the complete bipartite graph Kn,nare geodesic transitive for anyn≥1.These two graphs have diameter at most2.The Johnson graphs,Hamming graphs and Odd graphs are all geodesic transitive,and these graph families have both diameter and valency unbounded.Recently,Feng and Hua[13]presented a new family of locally geodesic transitive graphs with arbitrarily large diameter and valencies,containing a particular case to be geodesic transitive.

3.1 Comparison of distance,geodesic and arc transitivity for graphs

In this subsection,we comparesgeodesic transitivity of graphs with two other symmetry properties,namelysdistance transitivity andsarc transitivity.Given a graphΓand an integers≤diam(Γ),it is straightforward to verify that,ifΓissarc transitive then it issgeodesic transitive,which in turn implies that it issdistance transitive.These three properties are equivalent ifΓhas girth greater than2s,see Lemma3.2.The following discussion of this subsection will provide some insight into the differences between these transitivity properties.The diagram in Figure3gives the relationship of these three transitivities fors=2,and in the diagram,2 d.t,2 g.t and2 a.t stand for2 distance transitive graphs,2 geodesic transitive graphs and2 arc transitive graphs,respectively.

Figure3 Comparison

Note that eachigeodesic of a graph is aniarc.ThusΓis(G,s) arc transitive if and only if eachsarc is ansgeodesic,and this is true if and only if girth(Γ)≥2s.Thus the following result is true.

Lemma3.1LetΓbe a(G,s) geodesic transitive graph for someG≤Aut(Γ)and2≤s≤diam(Γ).ThenΓis(G,s) arc transitive if and only if girth(Γ)≥2s.

There exist infinite graphs which do not have the property of Lemma3.1 fors=2:the complete multipartite graphs Km[b]withm≥3andb≥2,have girth3,are2 geodesic transitive,but are not 2 arc transitive.

The next lemma provides a sufficient condition for a(G,s) distance transitive graph to be(G,s) geodesic transitive.

As each1 arc of a graph is a1 geodesic,geodesic transitive graphs are in particular1 arc transitive,and may or may not besarc transitive for somes＞1.The following theorem specifies the possiblesarc transitivities for geodesic transitive graphs,and is proved in[20].It follows from a deep result of Weiss[42],relying on the finite simple group classification,that if a finite graph of valency at least3issarc transitive but not(s+1) arc transitive thens∈{1,2,3,4,5,7}.

Theorem3.1Lets∈{1,2,3,4,5,7}.Then there are infinitely many geodesic transitive graphs that aresarc transitive but not(s+1) arc transitive.Moreover,such graphs exist with unboundedly large diameter if and only ifs∈{1,2,3}.

It showed in[20,Theorem1.2]that the Paley graphsP(q)and the Peisert graphsPei(q)are 2 distance transitive,and hence1 geodesic transitive,but are not2 geodesic transitive for most values ofq.These graphs have diameter2and are well known to be distance transitive.

Theorem3.2(1)Letq≡1(mod4)be a prime power.Then the Paley graphP(q)is distance transitive for allq,butP(q)is geodesic transitive if and only ifq=5or9.

(2)Letpbe a prime such thatp≡3(mod4)andq=pr≡1(mod4)whereris even.Then the Peisert graphPei(q)is distance transitive for allq,butPei(q)is geodesic transitive if and only ifq=9.

At this moment,it is only known examples of graphs which aresdistance transitive but notsgeodesic transitive fors=2,and so the following problem is interesting.

ProblemFind some(or infinitely many)sdistance transitive but notsgeodesic transitive graphs fors≥3.

3.2 Locally2 geodesic transitive graphs

For a graphΓand a positive integers≤diam(Γ),by the definitions ofsarcs andsgeodesics,eachsgeodesic is ansarc,and each1 arc is a1 geodesic.However,fors≥2,there may existsarcs that are notsgeodesics,for instance ifΓcontains a triangle,then2 arcs in a triangle are not2 geodesics(the 2 arc(u1,u2,u3)of the octahedron in Figure1is not a2 geodesic).One infinite family of graphs that is geodesic transitive but not2 arc transitive is the Johnson graphJ(n,k)with2≤k≤[]andn≥4,see[20,Proposition2.1].Thus the family of non complete locally2 arc transitive graphs is properly contained in the family of locally2 geodesic transitive graphs.If a non complete graphΓis locally2 arc transitive,then its girth is at least4,and so the subgraph[Γ(u)]induced onΓ(u)is an empty graph,for each vertexu.However,there are many locally2 geodesic transitive graphs whose neighbourhood subgraphs are not empty graphs.

The possible local structures of2 geodesic transitive graphs are characterized in2013,and the result shows that it is reasonable to distinguish three classes of locally(G,2) geodesic transitive graphs.

Theorem3.3([7,Theorem1.1 ])LetΓbe a connected non complete locally(G,2) geodesic transitive graph such that each vertex has valency at least2.Letube a vertex ofΓ.Then one of the following holds.

(1)ΓisGvertex transitive,girth(Γ)=3,[Γ(u)]is connected of diameter2,and the induced action ofGuonΓ(u)is transitive on vertices and on pairs of non adjacent vertices.

(2)ΓisGvertex transitive,[Γ(u)]∼=mKrfor some integersm≥2,r≥1.

(3)Γis notGvertex transitive;Γis bipartite with parts∆1and∆2,and there existm1,m2≥2such that for anyui∈∆i,[Γ(ui)]∼=miK1.

In[7],the authors also investigated in further detail the graphs in Theorem3.3 (2).For two positive integersm,r,the family of locallymKrgraphs is denoted byF(m,r),and for a graphΓ∈F(m,r),the clique graph ofΓis denoted byC(Γ).

Theorem3.4([7,Theorem1.4 ])LetΓbe a connected non complete graph andm≥2,r≥1be integers.Then the following two statements hold.

(1)Γ∈F(m,r)if and only ifΓis theSpoint graph of a partial linear spaceSof order(m,r+1)which contains no triangles.

Theorem3.5LetΓ∈F(m,r)withm≥2,r≥1and letG≤Aut(Γ).Then the following statements are equivalent.

(1)Γis(G,2) geodesic transitive.

There is a reduction theorem for the family of2 geodesic transitive graphs inF(m,r).

Theorem3.6LetΓ∈F(m,r)be a(G,s) geodesic transitive graph wherem,r,s≥2.IfGis not quasiprimitive onV(Γ),then there exists an intransitive normal subgroupNofGsuch that:Γis a cover of ΓN,G/Nis quasiprimitive onV(ΓN),and eitherΓN∼=Kmr+1isG/Narc transitive orΓN∈F(m,r)is non complete(G/N,s′) geodesic transitive wheres′=min{s,diam(ΓN)}.

Finally,there is also a reduction theorem for the family of2 geodesic transitive graphs which are locally connected.

Theorem3.7LetΓbe a connected(G,s) geodesic transitive graph which is also locally connected wheres≥2.Suppose thatΓis not isomorphic to Km[b]for anym≥3,b≥2.IfGis not quasiprimitive onV(Γ),thenGhas an intransitive normal subgroupNsuch thatΓis a cover ofΓN,G/Nis quasiprimitive onV(ΓN)andΓNis both(G/N,s′) geodesic transitive and locally connected,wheres′=min{s,diam(ΓN)}.

3.3 Two Geodesic transitive graphs of valency p or2p

LetΓbe an antipodal graph of diameterd.Then we may partition its vertices into sets,called fibres,such that any two distinct vertices in the same fibre are at distancedand two vertices in different fibres are at distance less thand.

For a finite groupG,a core free subgroupH(that is,

g∈G Hg=1),and an elementg∈Gsuch that

G=H,gandg2∈H,the coset graph Cos(G,H,HgH)is the graph with vertex set{Hx|x∈G},such that two verticesHx,Hyare adjacent if and only ifyx−1∈HgH.This graph is connected,undirected,andGarc transitive of valency|H:H∩Hg|,see[24].

Graphs in Definition3.2 have appeared a number of times in the literature.They were constructed by D.Taylor[38]as a family of regular two graphs(see[3,p.14]),they appeared in the classification of antipodal distance transitive covers of complete graphs in[16],and were also constructed explicitly as coset graphs and studied in[22].

The following two results classify the family of2 geodesic transitive graphs of prime valency.

Theorem3.8([8,Theorem1.2 ])(a)A graphΓ∈C(p)if and only ifΓis a connected non bipartite antipodal double cover of Kp+1withp≡1(mod4),and Aut(Γ)∼=PSL(2,p)×Z2.

(b)For a givenp,all graphs inC(p)are isomorphic,geodesic transitive but not2 arc transitive and have diameter3.

The second theorem shows that the graphs in Definition3.2 are the only2 geodesic transitive graphs of prime valency that are not2 arc transitive.

Theorem3.9([8,Theorem1.3 ])LetΓbe a connected non complete graph of prime valencyp.ThenΓis2 geodesic transitive if and only ifΓis2 arc transitive,orp≡1(mod4)andΓ∈C(p).

These two theorems show that forp=2or primep≡3(mod4),all connected2 geodesic transitive graphs of valencypare2 arc transitive,while for primep≡1(mod4),up to isomorphism,there is a unique connected2 geodesic transitive graph of valencypthat is not2 arc transitive.

In the same year,in[18]it gives a classification of the family of2 geodesic transitive graphs of valency2pwherepis an odd prime.

LetΓ1,Γ2be two graphs.Then the graphΓ1[Γ2]is the lexicographic product ofΓ1andΓ2,its vertex set isV(Γ1)×V(Γ2),and two vertices(v1,v2),(u1,u2)are adjacent inΓ1[Γ2]if and only if,eitherv1,u1are adjacent inΓ1,orv1=u1andv2,u2are adjacent inΓ2.

Definition3.3LetΓbe a connected vertex transitive graph with2nvertices.Suppose that Aut(Γ)hasnblocks of cardinality2inV(Γ),say∆i={vi,},i=1,2,...,n,and[∆i]∼=K2.Suppose that fori=j,viis adjacent tovjif and only ifviis adjacent to.

We define a graph Γto be the graph with vertex set{∆1,...,∆n},and two vertices∆i,∆jare adjacent if and only if,there exist a vertex of∆iand a vertex of∆jthat are adjacent inΓ.Then Γis a graph withnvertices.

The following result gives a classification of the family of connected2 geodesic transitive graphs of valency2p.

Theorem3.10LetΓbe a non complete connected2 geodesic transitive graph of valency2pwherepis an odd prime.LetA=Aut(Γ)andu∈V(Γ).Then one of the following holds.

(1)Γis locally primitive of girth3,andΓis one of the following graphs:the halved5 cube,the complement of the triangular graphT(7),the Conway Smith graph or the Hall graph.

(2)Γis locally imprimitive of girth3,andΓ∈{K3[p],K(p+1)[2]},orΓ∈F(p,2),or one of the following is true.

(2.1 )Γis a line graph and[Γ(u)]∼=K2□Kp.

(2.2)Γis a line graph,Auhas two blocks of cardinalitypinΓ(u)but does not have blocks of cardinality2,and the subgraph induced by a block is isomorphic to Kp.

(2.3 )Auhaspblocks,∆i={vi,},i=1,...,p,inΓ(u)but does not have blocks of cardinalityp,Σ:=[Γ(u)]is connected and[∆i]∼=K2.Either[∆i∪∆j]∼=C4wheneveri=j,|Σ(vi)|=pand Σ(vi)=Σ2()∪{};or Σ∼=[K2],whereas in Definition3.3 ,is a vertex transitive graph ofpvertices with valency2(p−1)/3or(p−1)/2.

(3)Γhas girth at least4and is2 arc transitive.

3.4 Line graphs and s geodesic transitivity

The first theorem of this subsection is an investigation of the connections between thesarc transitivity of a connected graphΓand the(s−1) geodesic transitivity of its line graphL(Γ)wheres≥2.A key ingredient in this study is a collection of injective mapsLs,whereLsmaps thesarcs ofΓ to certainstuples of edges ofΓ(vertices ofL(Γ)).The main consequence linking the symmetry ofΓandL(Γ)is given in the following theorem.

Theorem3.11([6,Theorem1.1 ])LetΓbe a connected regular,non complete graph of girth g and valency at least3.LetG≤Aut(Γ)and letsbe a positive integer such that2≤s≤diam(L(Γ))+1.ThenΓis(G,s) arc transitive if and only ifs≤g/2+1andL(Γ)is(G,s−1) geodesic transitive.

It follows from a deep theorem of Weiss in[42]that ifΓis a connectedsarc transitive graph of valency at least3,thens≤7.This observation yields the following corollary.

Corollary3.1LetΓand g be as in Theorem3.1 1.Letsbe a positive integer such that2≤s≤diam(L(Γ))+1.IfL(Γ)is(s−1) geodesic transitive,then either2≤s≤7ors＞max{7,g/2+1}.

Connected arc transitive graphs of valency at most3(for valency3case we also require that its girth is3)have simple structures.IfΓhas valency1,thenΓ∼=K2;ifΓhas valency2,thenΓ∼=Cn;ifΓ has both valency and girth3,thenΓ∼=K4.Graphs that are2 geodesic transitive with the next smallest valency,that is,valency4,is the first interesting family to study.As an application of Theorem3.11,there is a characterization of connected non complete2 geodesic transitive graphs of valency4.We denote the octahedron byOwhich is the complete multipartite graph K3[2].

Theorem3.12([6,Theorem1.3 ])LetΓbe a connected non complete graph of valency4.ThenΓ is2 geodesic transitive if and only ifΓis one of the following:

(1)Γis2 arc transitive;

(2)Γ=L(K4)∼=O;

(3)Γ=L(Σ)for a connected3 arc transitive cubic graph Σ.

Moreover,Γis geodesic transitive of girth3if and only ifΓ=L(Σ)for a cubic distance transitive graph Σ,namely Σ=K4,K3,3,the Petersen graph,the Heawood graph or Tutte’s8 cage.

Since there are infinitely many3 arc transitive cubic graphs,there are therefore infinitely many 2 geodesic transitive graphs with girth3and valency4.Theorem3.12 provides a useful method for constructing2 geodesic transitive graphs of girth3and valency4which are not geodesic transitive,an example being the line graph of a triple cover of Tutte’s8 cage constructed in[27].The line graphs mentioned in the third part of Theorem3.12 are precisely the distance transitive graphs of valency4and girth3given,for example,in[3,Theorem7.5.3 (i)]and[35,Theorem].

3.5 Two Geodesic transitive Cayley graphs

In Theorem3.3,it is proved that a(G,2) geodesic transitive graph is either locally connected or in the familyF(m,r)for somem≥2,r≥1.Further,in Subsection5.1,it gives reduction results for both families separately,which highlights the role of a subfamily of‘basic’examples,many of which are Cayley graphs.The aim of this subsection is to introduce(not necessarily basic)Cayley graphs which are(G,2) geodesic transitive relative to a groupGwhich demonstrates both the transitivity on2 geodesics,and the property of being a Cayley graph.Such graphs are said to be normal(G,2) geodesic transitive(see Definition3.4).The philosophy behind this approach is similar to that in[31]and[44].The analysis identifies both the fundamental role of innately transitive groupsGand the exceptional role of complete multipartite graphs in this study.

LetΓ:=Cay(T,S)be a Cayley graph.Then the groupR(T)={σt|t∈T}of right translationsσt:x →xtis a subgroup of the automorphism group Aut(Γ)and acts regularly on the vertex set.We may identifyTwithR(T).Godsil[15,Lemma2.1]observed thatNAut(Γ)(T)=T:Aut(T,S)where Aut(T,S)={σ∈Aut(T)|Sσ=S}.If Aut(Γ)=NAut(Γ)(T),then the graphΓwas called a normal Cayley graph by Xu[44]and such graphs have been studied under various additional conditions on their order or valencies,for example in[11,21,25].In any case,T:Aut(T,S)is the largest subgroup of Aut(Γ)which witnesses thatΓis a Cayley graph forT.

Definition3.4LetΓ=Cay(T,S)for a finite groupTand a subsetS⊊T{1},S=S−1.ThenΓis said to be normal2 geodesic transitive if it is(G,2) geodesic transitive for a groupGsatisfyingT≤G≤T:Aut(T,S).We also say thatΓis normal(G,2) geodesic transitive if we wish to specify the groupG.

There are many normal(G,2) geodesic transitive Cayley graphs.One simple example is Cay(T,S)whereT=a ∼=Zrfor somer≥4,S={a,a−1},andG=T:HwhereH=αwithα:a →a−1.The analysis of the family of graphs follows two lines of attack,one local and the other a global structural description.The former approach identifies the cycleCrand the complete multipartite graph K4[2](the graph in Figure4)as exceptions.The first theorem gives a general characterization of normal(G,2) geodesic transitive Cayley graphs.

Figure4 K4[2]

Theorem3.13([9,Theorem1.2 ])LetΓ=Cay(T,S)be a normal(G,2) geodesic transitive Cayley graph.Then one of the following holds.

(1)Γ∼=CrandT∼=Zrfor somer≥4.

(2)Γ∼=K4[2],T∼=Q8andS=T(T).

(3)There is a primepand an integerqsuch that for alla∈S,o(a)=panda {1}⊊S,ando(b)=qfor eachb∈S2(S∪{1}).

The reduction method works very well in the study of symmetric graphs and locally symmetric graphs.This involves so called quasiprimitive actions which were first defined and classified by Praeger in[29].She divides finite quasiprimitive permutation groups into8types analogous to the O’Nan Scott types of finite primitive permutation groups(see Section2.3).This has been a powerful tool for a lot of work on the study of symmetric or locally symmetric graphs,see for example[5,12,14].

We recall some definitions.LetΓbe aGvertex transitive graph.IfNis a non transitive normal subgroup ofG,then the set ofNorbitsB={B1,B2,...,Bn}forms aGinvariant partition ofV(Γ).The quotient graphΓNofΓis the graph with vertex setBsuch thatBi,Bjare adjacent inΓNif and only if there existx∈Bi,y∈Bjsuch thatx,yare adjacent inΓ.Further,Γis said to be a cover ofΓNif for each edge{Bi,Bj}ofΓNandv∈Bi,we have|Γ(v)∩Bj|=1.The next theorem is a reduction result,which highlights the exceptional nature of the graphs Km[b].

Theorem3.14([9],Theorem1.3 )LetΓ=Cay(T,S)be a normal(G,2) geodesic transitive Cayley graph.IfTis not a minimal normal subgroup ofG,then there exists a normal subgroupNofGsuch thatN＜Tand one of the following holds.

(1)Γ∼=Kqf[pe]for primesp,qand integerse,f,andΓN∼=Kqf.

(2)Γis bipartite,(G,2) arc transitive andΓN∼=K2.

(3)Γis a cover ofΓN∼=Cay(T/N,SN/N),whereT/Nis a minimal normal subgroup ofG/N.Further,eitherΓN∼=K|S|+1isG/Narc transitive,orΓNis normal(G/N,2) geodesic transitive.

Remark3.2(1)Although all the graphsΓ=Kqf[pe]in Theorem3.14 (1)are(G,2) geodesic transitive forG=Aut(Γ),the requirement to be normal(G,2) geodesic transitive places strong restriction on both the groupTand the parametersqf,pe.For example,by Theorem 3.13,K4[2]is a normal2 geodesic transitive Cayley graph forQ8,while the octahedron K3[2]although 2 geodesic transitive is not normal2 geodesic transitive.We will investigate further those complete multipartite graphs which are normal2 geodesic transitive,see Theorem3.1 5.

(2)As mentioned in the previous,(G,2) arc transitive graphs have been studied intensively,so this theorem may genuinely be viewed as a reduction pathway for investigating normal(G,2) geodesic transitive Cayley graphs.The study of such graphs arising in Theorem3.14 (3)reduces to the following three problems:investigating the case thatTis a minimal normal subgroup ofG,studying the 2 geodesic transitive covers of these graphs,and investigating the2 geodesic transitive covers of complete graphs.In the first problem,the groupGis innately transitive onV(Γ)with a regular minimal normal subgroupT.Innately transitive groups have been classified in[1]in the same spirit as the O’Nan Scott Theorem for primitive groups.

Letpbe a prime anda,nbe positive integers.Then apgroupGis called a specialpgroup if its centerZand derived subgroup coincide and bothZandG/Zare elementary abelian;pis called a primitive prime divisor ofan−1ifpdividesan−1but does not divideai−1for anyi＜n.We also recall that a transitive groupGon a set Ω is a Frobenius group ifGx=1,butGx,y=1for anyx=y∈Ω.

The following result investigates further the complete multipartite graphs which are normal 2 geodesic transitive.

Theorem3.15([9,Theorem1.5 ])Suppose thatΓ∼=Km[b](m≥3,b≥2)is a normal(G,2) geodesic transitive Cayley graph Cay(T,S).Then one of the following holds.

(1)m=4,b=2andT=Q8.

(2)mbis a power of a primep,andTis either elementary abelian or a specialpgroup of exponentp.

(3)m=q,b=pefor distinct primesp,qsuch thatq−1dividese,qis a primitive prime divisor ofpq−1−1andT=:Zqis a Frobenius group with Zqacting as a group ofFpq−1scalar transformations on.Moreover,G=T.G0with≤G0≤AΓL(e/(q−1),pq−1)andG0induces the full group of field automorphisms ofFpq−1.

Conversely,for all parametersm,bas in(1),(2)or(3),there exists at least one tripleT,S,Gsuch that the graph Km[b]is a normal(G,2) geodesic transitive Cayley graph Cay(T,S).