Infinite primitive directed graphs

DOI 10.1007/s10801-009-0190-3

Infinite primitive directed graphs

Simon M. Smith

Received: 26 January 2006 / Accepted: 8 June 2009 / Published online: 28 July 2009

© Springer Science+Business Media, LLC 2009

Abstract A groupGof permutations of a setis primitive if it acts transitively on , and the onlyG-invariant equivalence relations onare the trivial and universal relations.

A digraphis primitive if its automorphism group acts primitively on its vertex set, and is infinite if its vertex set is infinite. It has connectivity one if it is connected and there exists a vertexαof, such that the induced digraph\{α}is not connected.

Ifhas connectivity one, a lobe ofis a connected subgraph that is maximal subject to the condition that it does not have connectivity one. Primitive graphs (and thus digraphs) with connectivity one are necessarily infinite.

The primitive graphs with connectivity one have been fully classified by Jung and Watkins: the lobes of such graphs are primitive, pairwise-isomorphic and have at least three vertices. When one considers the general case of a primitive digraph with connectivity one, however, this result no longer holds. In this paper we investigate the structure of these digraphs, and obtain a complete characterisation.

Keywords Primitive·Graph·Digraph·Permutation·Group·Orbital graph· Orbital digraph·Block-cut-vertex tree

1 Preliminaries

Throughout this note, a graph will be a pair(V , E), where V is the set of vertices of, and Ethe set of edges. The setE consists of unordered pairs of distinct elements ofV .

A digraph is a pair(V , A), where A is the set of arcs of . Each arc is an ordered pair of distinct elements ofV . All paths in a digraph will be undi-

S.M. Smith (

Mathematical Institute, University of Oxford, Oxford, UK e-mail:[email protected]

rected, unless otherwise stated. A directed cycle inis a pathα₀α₁. . . α_n such that (α_n, α₀)∈Aand(α_i, α_i+1)∈Afor all integersisatisfying 0≤i < n.

All graphs and digraphs will be free of loops and multiple edges. They are said to be infinite if their vertex sets are infinite.

The distance between two connected verticesαandβin a graph or digraphwill be denoted byd(α, β).

Groups, and in particular groups of automorphisms, will play a leading role in many of the arguments presented herein. Throughout this work,Gwill be a group of permutations of a set, wherewill usually be the vertex set of some infinite digraph.

Ifα∈andg∈G, we denote the image of αunder g byα^g. Following this notation, all permutations will act on the right. The orbit ofαunder the action ofG will be denoted byα^G.

Ifα∈, we denote the stabiliser ofαinGbyG_α, and if⊆we denote the setwise and pointwise stabilisers ofinGbyG_{}andG₍₎respectively.

A transitive groupGis primitive onif the onlyG-congruences admitted by are the trivial and universal equivalence relations; otherwiseGis said to be imprimi- tive. It is said to act regularly onifG_α=1 for eachα∈.

A subset of is called a block if for all g∈G we have either ^g=or ^g∩= ∅. A block is called trivial if || =1, and proper if =. Since the existence of a non-trivial proper block permits the construction of a non-trivial and non-universalG-congruence on, the groupGis primitive if and only ifdoes not contain a non-trivial proper block.

The following is well known, and is often a very useful test for primitivity.

Theorem 1.1 [1, Theorem 4.7] IfGis a transitive group of permutations on, and

||>1, thenGis primitive onif and only if, for everyα∈, the stabiliserGα is a maximal subgroup ofG.

A graph or digraphis primitive if its automorphism group Autacts primitively on the setV , and is automorphism-regular if Autacts regularly onV .

A primitive graph or digraphwith at least one edge or arc is always connected.

Indeed, the connected components ofform a set of Aut-congruence classes.

The connectivity of an infinite connected graph or digraphis the smallest pos- sible size of a subsetW ofV for which the induced graph\W is disconnected.

A lobe ofis a connected subgraph that is maximal subject to the condition it has connectivity strictly greater than one. Ifhas connectivity one, then the verticesα for which\ {α}is disconnected are called the cut vertices of.

2 Local structure

Consider the following construction. LetV₁be the set of cut vertices of a connected graph, and letV₂ be a set in bijective correspondence with the set of lobes of. We letT be a bipartite graph whose parts areV₁andV₂. Two verticesα∈V₁and x∈V₂are adjacent inT if and only ifαis contained in the lobe ofcorresponding

tox. In fact, this construction yields a tree, which is called the block-cut-vertex tree of. Note that ifhas connectivity one and block-cut-vertex treeT, then any group Gacting onhas a natural action onT.

It is perhaps helpful to the reader at this point to describe a graph that is typical of those in which we are interested. LetP₅denote the Petersen Graph. To each vertex αin P₅ we adjoin another two copies ofP₅ in such a way thatαis contained in three distinct copies ofP₅that intersect only inα. We continue this process for each additional vertex whenever a newP₅ is adjoined. In this way we obtain an infinite graph with connectivity one, whose lobes are isomorphic toP5. The block-cut-vertex tree of this graph is a biregular tree, in which one set of the natural bipartition has valency 3, and the other valency 10. As we shall see, this graph is primitive.

Letbe a primitive digraph with connectivity one whose lobes have at least three vertices, and supposeGis a vertex- and arc-transitive group of automorphisms of. Sinceis vertex-transitive with connectivity one, every vertex is a cut vertex. Fix some lobe of , and let H be the subgroup of the automorphism group Aut induced by the setwise stabiliserG_{} ofV inG. LetT be the block-cut-vertex tree of, and letxbe the vertex ofT that corresponds to the lobe. Our aim in this section is to showHis primitive but not regular.

Ifx1andx2are distinct vertices of the treeT, we useC(T \ {x1}, x2)to denote the connected component ofT\ {x1}that contains the vertexx2.

Lemma 2.1 IfGacts primitively on the vertices of, thenH acts primitively on the vertices of.

Proof If H acts transitively but not primitively on V , then there exists a non- trivial proper block⊆V . For any two distinct verticesα, β∈, the digraph (V , (α, β)^H)is not connected, since it does not contain a path fromαto any vertex inV \.

If H does not act transitively on V , then one may choose distinct vertices α, β, γ ∈V such that β ∈α^H butγ /∈α^H. Again the digraph(V , (α, β)^H)is not connected, as there is no path fromαtoγ. Thus, ifHis not transitive onV , or ifHis transitive but not primitive onV , then there exist distinct verticesα, β∈V such that the digraph:=(V , (α, β)^H)is not connected.

Suppose this is the case, and choose distinct verticesα, β∈V such that is not connected. We will show this assumption implies the digraph:=(V , (α, β)^G) cannot be connected, and is therefore not primitive; whenceGcannot be primitive.

Recall thatT is the block-cut-vertex tree of and x is the vertex of T corre- sponding to the lobe. Let{i}i∈I be the set of connected components ofand let

Ci:=

δ∈_i

C(T \ {x}, δ)∩V .

Supposeδ_i ∈Ci andδ_j∈Cj, withi=j. We claimδ_i andδ_j are not adjacent in. Indeed, since the distanced_T(α, β)betweenαandβ inT is equal to 2, ifδ_i andδ_j are to be adjacent in the arc-transitive digraph , it must be the case that d_T(δ_i, δ_j)=2. If eitherδ_i orδ_j is not adjacent toxinT thend_T(δ_i, δ_j) >2, so they

cannot be adjacent in. On the other hand, ifδ_i andδ_j are adjacent tox inT, then they both lie inV =V , and thereforeδ_i ∈_i andδ_j ∈_j. In this case, if they are adjacent inthen there existsg∈Gsuch that either(δi, δj)or(δj, δi)is equal to(α, β)^g. Such an automorphism must fixV setwise, and therefore lies inG_{}. Thus, there exists an elementh∈H such that either(δ_i, δ_j)or (δ_j, δ_i)is equal to (α, β)^h, meaning thatδ_i andδ_j are adjacent in; however, this contradicts the fact thatδi andδj are in distinct components of . Hence,δi andδj are not adjacent in.

Hence, there can be no path inbetween a vertex inCi and a vertex inCjwhen- everi=j, and so the digraphis not connected. Whence, cannot be primitive,

andGcannot act primitively onV .

Fix distinct verticesα, β∈V and recall thatα andβ are also vertices of the block-cut-vertex treeT.

A geodesic between two vertices is a shortest path between them. In a tree, there is a unique geodesic between any two vertices. Let[α, β]T be theT-geodesic between αandβ, and let(α, β)_T be theT-geodesic[α, β]T excluding bothα andβ. This notation extends obviously to[α, β)T and(α, β]T.

Sinceαandβ are vertices of bothandT, the distanced_T(α, β)is even, so we may choose a vertexy∈(α, β)_T that is distinct fromαandβ.

Lemma 2.2 Ifg∈G_α does not fixy∈V T, andδ /∈C(T \ {y}, α), thenδ^g∈/C(T \ {y}, β).

Proof Ifδ /∈C(T\ {y}, α)andδ^g∈C(T\ {y}, β)thenδ, δ^g∈/C(T \ {y}, α), so we

must haveg∈G_α,y.

Lemma 2.3 If g ∈G_α does not fix the vertex y and δ /∈ C(T \ {y}, α) then dT(y, δ^g) > dT(y, δ).

Proof Ifδ /∈C(T\{y}, α)theny∈ [α, δ]T. Thusd_T(δ, δ^g)=d_T(δ, y)+d_T(y, y^g)+ dT(y^g, δ^g)anddT(δ, δ^g)=dT(δ, y)+dT(y, δ^g). ThereforedT(y, δ^g)=dT(y^g, δ^g)+ d_T(y, y^g). Now d_T(y^g, δ^g)=d_T(y, δ), and d_T(y, y^g)≥1. Whence d_T(y, δ^g) >

d_T(y, δ).

Henceforth, ifH is a subgroup ofG, then we will writeH≤G; if we wish to exclude the possibility ofH=Gwe will instead writeH < G.

Lemma 2.4 Letg₁, . . . , g_n∈G_α andh₁, . . . , h_n∈G_β, and supposeG_α,y=G_β,y. If there exists γ ∈V T such that G_α,y ≤G_γ then, for some m≤n, there exist g₂, . . . , g_m ∈Gα\Gyandg₁ ∈Gα\Gy∪ {1}together withh₁, . . . , h_m−1∈Gβ\Gy

andh_m∈G_β\G_y∪ {1}such that

γ^g1h1...gmhm=γ^g1h1...gnhn.

Proof The proof of this lemma will be an inductive argument. Suppose there exists γ∈V T such thatG_α,y≤G_γ.

Letn=1. When consideringh₁∈G_β we have two cases: eitherh₁∈G_yorh₁∈ G_β\G_y. Ifh1∈G_y thenh1∈G_β,y =G_α,y, sog1h1∈G_α. In this case, redefine g1:=g1h1and seth₁:=1. Alternatively, ifh1∈G_β\G_ythen seth₁:=h1. Having found a suitableh₁, we will now constructg₁from the (possibly redefined) element g₁∈G_α. We again have two cases: either g₁∈G_y or g₁∈G_α \G_y. If g₁∈G_y theng₁∈G_α,y and sog₁∈G_γ. In this case we can choose g₁ :=1. Otherwise, if g₁∈G_α\G_y, then chooseg₁ :=g₁. In choosingg₁andh₁in this way we ensure that

γ^g1h1=γ^g1h1, so the hypothesis holds whenn=1.

Letkbe a positive integer, and suppose the hypothesis is true for all integersn≤k.

Fixg₁, . . . , g_k+1∈G_αandh₁, . . . , h_k+1∈G_β, and set γ:=γ^{g1h1...gk+1hk+1}.

We will use induction to construct elementsg₂, . . . , g_m∈G_α\G_y andg₁ ∈G_α \ G_y∪ {1}together withh₁, . . . , h_m−1∈G_β\G_yandh_m∈G_β\G_y∪ {1}such that

γ^g1h1...gmhm=γ, wheremis some integer less than or equal tok+1.

We begin by consideringh_k+1∈G_β. There are two cases: either h_k+1∈G_y or h_k+1∈G_β \G_y. Ifh_k+1∈G_y thenh_k+1∈G_β,y =G_α,y, so g_k+1h_k+1∈G_α. In this case, redefineg_k+1:=g_k+1h_k+1and seth:=1. If, on the other hand,h_k+1∈ Gβ\Gy, then seth:=hk+1.

If we now consider the (possibly redefined) elementgk+1∈Gα, there are again two cases: eitherg_k+1∈G_y, org_k+1∈G_α\G_y. Ifg_k+1∈G_y theng_k+1∈G_α,y= G_β,y, soh_kg_k+1h∈G_β. In this case, leth:=h_kg_k+1h; then

γ=γ^g1h1...gkh,

so we can apply the induction hypothesis toγ^g1h1...gkh and we are done. If, on the other hand,g_k+1∈G_α\G_y, then setg:=g_k+1, and observe

γ=γ^{g1h1...gkhkgh}.

By the induction hypothesis, for somel≤kthere existg₂, . . . , g_l∈Gα\Gyand g₁ ∈G_α\G_y∪ {1}together with h₁, . . . , h_l−1∈G_β \G_y andh_l∈G_β\G_y∪ {1}

such that

γ^g1h1...gkhk=γ^g1h1...glhl.

At this final stage in the proof, we again face two possibilities: eitherh_l=1 or h_l∈Gβ\Gy. In the first instance defineg:=g_lh_lg, soγ=γ^{g1h1...gl−1hl−1gh}. Sinceg=g_lg∈Gαandh∈Gβandl≤k, we may apply the induction hypothesis.

On the other hand, ifh_l∈G_β \G_y, then setg_l+1:=g∈G_α\G_y andh_l+1:=

h∈G_β\G_y∪ {1}, and observeγ=γ^{g1h1...gl+1 hl+1}. Nowl≤k, so definingmto be

l+1 we havem≤k+1. Thus in both cases the hypothesis holds. It is therefore true

forn=k+1.

We are now in a position to present the main result of this section which describes necessary conditions for a vertex-transitive subgroup of the automorphism group of an infinite primitive digraph with connectivity one to be imprimitive.

Theorem 2.5 LetGbe a vertex-transitive group of automorphisms of a connectivity- one digraphwhose lobes have at least three vertices, and letT be the block-cut- vertex tree of. If there exist distinct verticesα, β∈V such that, for some vertex x∈(α, β)T,

G_α,x=G_β,x,

thenGdoes not act primitively onV .

Proof SupposeGacts primitively onV and there exist distinct verticesα, β∈V and x ∈ (α, β)_T such that G_α,x =G_β,x. We will begin by showing the group G_α, G_βgenerated byG_α andG_β is not equal toG; then we shall show it is not equal toG_α. Whence,G_α <G_α, G_β< G which, by applying Theorem1.1, will contradict the assumption thatGis primitive.

Without loss of generality, supposedT(x, α)≤dT(x, β). If the orbit β^Gα,Gβ containsα, then there exist elementsg₁, . . . , g_n∈G_αandh₁, . . . , h_n∈G_β such that α=β^g1h1...gnhn. By Lemma2.4, we can findm≤nandg₂, . . . , g_m∈G_α\G_x and g₁ ∈G_α\G_x∪ {1}together withh₁, . . . , h_m−1∈G_β\G_x andh_m∈G_β\G_x∪ {1}

such that

α=β^g1h1...gmhm.

Suppose these automorphisms are chosen so thatmis minimal.

Now eitherg₁ ∈G_α\G_xorg₁ =1. Ifg₁ =1 thenβ^g1 =βand thereforeβ^g1h1= β. Thusβ^g2h2...gmhm=α, contradicting the minimality ofm. So we must haveg₁∈ G_α\G_x. Sinceβ /∈C(T \ {x}, α), we may apply Lemma2.2 and Lemma2.3to obtaind_T(x, β^g1) > d_T(x, β)andβ^g1∈/C(T \ {x}, β).

We now observeh₁=1. Indeed, ifh₁=1 thenm=1 andα=β^g1; sinceg₁ ∈Gα

this is clearly not possible.

Thus,h₁∈G_β \G_x andβ^g1 ∈/C(T \ {x}, β), and we can again deduce from Lemma2.2and Lemma2.3thatd_T(x, β^g1h1) > d_T(x, β^g1) > d_T(x, β), andβ^g1h1∈/ C(T\ {x}, α).

We may continue to apply Lemmas2.2and2.3to obtainβ^g1h1...gm∈/C(T\{x}, β) anddT(x, β^g1h1...gm ) > dT(x, β). Now eitherh_m∈Gβ\Gxorh_m=1. Ifh_m=1 then α=β^g1h1...gm , and sod_T(x, α)=d_T(x, β^g1h1...gm ) > d_T(x, β). Ifh_m∈G_β\G_xthen, by Lemma2.3,d_T(x, β^g1h1...gmhm) > d_T(x, β); that is,d_T(x, α) > d_T(x, β). Thus, in both casesd_T(x, α) > d_T(x, β). This contradicts our assumption thatd_T(x, α)≤ dT(x, β). Hence α /∈β^Gα,Gβ, and so Gα, Gβ cannot act transitively on the set V . This ensures thatGα, Gβ =G.

By Theorem1.1, we must therefore haveG_α, G_β =G_α. Thus, the set of vertices Fix(Gα)fixed byG_αcontains bothαandβ. This set is a block of imprimitivity. Thus,

every vertex inV must be fixed byG_α, and soG_α= 1. However,G_αis a maximal subgroup ofG, soG_α= 1 implies thatGis a finite cyclic group of prime order.

This, however, is impossible, asGacts transitively on the infinite setV .

HenceG_α, G_β =G_α, andG_α, G_β =G, which contradicts our assumption that

Gis primitive.

Theorem 2.6 LetGbe a vertex-transitive group of automorphisms of a connectivity- one digraphwhose lobes have at least three vertices. IfGacts primitively onV andis some lobe ofthenG_{}is primitive and not regular onV .

Proof SupposeG acts primitively onV , and is a lobe of . By Lemma2.1, G_{} acts primitively onV . Suppose this action is regular. IfT is the block-cut- vertex tree of then there exists a vertex x∈V T corresponding to the lobe . Choose distinct vertices α and β in V , and observe G_α,x =G_α,{}≤G_β and G_β,x=G_β,{}≤G_α; furthermore, x∈(α, β)_T. This, however, is impossible, as it

impliesGis imprimitive by Theorem2.5.

3 Global structure

In this section we shall employ Theorem2.6to give a complete characterisation of the primitive connectivity-one digraphs.

Lemma 3.1 Suppose is a vertex-transitive digraph with connectivity one, whose lobes are vertex-transitive, have at least three vertices and are pairwise isomorphic.

Ifγ is a vertex in some lobeofandα∈V isγ or lies in a component of \ {γ}distinct from the component containingV \ {γ}, then the subgroup of Aut induced by the action of(Aut)_α,{}onis(Aut)_γ, and the group induced by the action of(Aut)_{}onis Aut.

Proof LetT denote the block-cut-vertex tree of, and letbe a lobe of. Choose γ ∈V and let C be a component of\ {γ}distinct from that which contains V \ {γ}. LetC be the subgraph ofinduced byC∪ {γ}, and supposeαis any vertex inC.

We begin by asserting that if₁and₂are lobes of, andα₁andα₂are vertices in₁and₂respectively, then there exists an isomorphismρ:₁→₂such that α₁^ρ=α2. Indeed, by assumption there exists an isomorphismρ:1→2. Define α₁ :=α^ρ₁. Since the lobe₂is vertex-transitive, there exists an automorphismτ of 2such thatα₁^τ =α2. Letρ:=ρτ. Thenρ:1→2 is an isomorphism, with α₁^ρ=α^ρ₁^τ=α₁^τ =α2.

Letx be the vertex ofT that corresponds to. For k≥0, definek to be the subgraph ofinduced by the set{ξ∈V |dT(x, ξ )≤2k+1}, andCk:=C∩k. Note that0=. We will show any automorphismσk :k→k which fixesCk

admits an extensionσ_k+1:_k+1→_k+1which fixesC_k+1.

Fixk≥0 and letσ_k:_k →_k be an automorphism that fixesC_k pointwise; in particular,σ₀∈(Aut)_γ. Let{α_i}i∈I be the set of vertices inV _k\V _k−1(where

V ₋₁:= ∅). Each vertexα_i belongs to a unique lobe_i of _k, and, if k≥1, the lobe_i possesses precisely one vertex in_k−1. Sinceis vertex transitive, any two vertices lie in the same number of lobes of, so let{_i,j}j∈J be the set of lobes of that containα_i and are distinct from_i. Each lobe_i,j is wholly contained in_k+1 and has exactly one vertex ink, namelyαi. Ifi∈I, setα_i:=α_i^σk and_i :=^σ_i^k. Then_i =_i for some i∈I. For all j ∈J there exists an isomorphism ρi,j : _i,j→_i,j such thatα_i^ρi,j =α_i. Thus, we may define a mappingσ_k+1:_k+1→ _k+1with

β^σk+1:=

⎧⎪

⎨

⎪⎩

β^σk ifβ∈V _k; β ifβ∈C;

β^ρi,j ifβ∈V _i,j\C.

This is clearly a well-defined automorphism of_k+1.

Hence ifσ0∈(Aut)_γ, then we may extend it to an automorphismσ ofthat fixesCpointwise, and therefore fixesα. Since each automorphism in(Aut)_γ may be extended in this way, the subgroup of Autinduced by(Aut)_α,{}must contain (Aut)_γ. Clearly no automorphism ofmay fix αandsetwise whilst not also fixingγ, so these two groups must in fact be equal.

We now adjust the above argument to show that the group induced by the action of(Aut)_{}onis Aut. Fixk≥0 and consider an automorphismσ_k:_k→_k that fixesV setwise; in particular,σ0∈(Aut).

Using the above notation, we may define a mapσk+1:k+1→k+1with

β^σk+1:=

β^σk ifβ∈V _k; β^ρi,j ifβ∈V i,j.

This is a well-defined automorphism ofk+1. Thus we may extend any automor- phismσ0∈(Aut) to an automorphismσ of that fixessetwise. Whence the group induced by the action of(Aut)_{}onis Aut. The primitive graphs with connectivity one have the following complete charac- terisation.

Theorem 3.2 [3, Theorem 4.2] Ifis a vertex-transitive graph with connectivity one, then it is primitive if and only if the lobes ofare primitive, pairwise isomorphic and each has at least three vertices.

Jung and Watkins’ result, while impressive, cannot be applied to primitive di- graphs without some modification. Indeed, consider the following counterexample.

Letbe the connectivity-one primitive graph whose lobes are undirected 3-cycles, in with each vertex lies in precisely two lobes. It is of course possible to verify this graph is primitive using Theorem3.2.

We assign to each vertex inthe label 1, 2 or 3 in such a way that no two vertices in a common lobe ofshare the same label. Whence, each lobe ofhas a vertex labelled 1, a vertex labelled 2 and a vertex labelled 3.

For each lobe inwe replace its edge set with a set of three arcs, from the vertex labelledito the vertex labelled(i+1)mod 3, fori=1,2,3. In this way we obtain a vertex-transitive connected digraphwhose vertex set isV . Furthermore, the lobes of this digraph are primitive, pairwise isomorphic, and have at least three vertices.

However, the set of vertices labelled 1 is a non-trivial proper block of the group Aut, so this group cannot act primitively on the digraph.

The approach taken by Jung and Watkins in their proof of Theorem3.2is broadly similar to the argument presented thus far. They first prove that any automorphism of a lobeof a vertex-transitive graphwith connectivity one may be extended to an automorphism of. It is then shown that if the lobes ofare vertex primitive, have at least three vertices, and are pairwise isomorphic, thenis primitive. It is here that their proof fails to apply to digraphs; by citing Theorem 1 of [2] they claim the lobes ofcannot be automorphism-regular. While this is indeed true of graphs, it is not true of digraphs, as our previous example illustrates.

Imrich’s result states that the automorphism group of a graph with more than two vertices cannot be regular and primitive. It relies on two results, Lemmas 2 and 3 of [2]. Lemma 2 is the well-known result that a regular primitive group of permutations must be cyclic; Lemma 3 states that any transitive abelian automorphism group of a non-trivial graph is the direct product of two cyclic groups of order 2. Any primitive and regular automorphism group of a graph must therefore equal this direct product;

Imrich shows that no such graph exists, and correctly deduces that automorphism- regular primitive graphs are not possible. It is in the proof of the latter lemma that Imrich’s result ceases to be applicable to digraphs: his argument requires the exis- tence of a specific graph automorphismψ. On inspection it transpires thatψis not a digraph automorphism, since it reverses the direction of edges. Thus Theorem 1 of [2] is not applicable to digraphs, which in turn causes Jung and Watkins’ result to fail.

Although their result does not extend immediately to digraphs, a complete char- acterisation is still possible.

Theorem 3.3 Ifis a vertex-transitive digraph with connectivity one, then it is prim- itive if and only if the lobes ofare primitive but not automorphism-regular, pairwise isomorphic and each has at least three vertices.

Proof Letbe a vertex-transitive digraph with connectivity one. Suppose the lobes ofare primitive but not automorphism-regular, pairwise isomorphic and each has at least three vertices. Let≈be an Aut-congruence onV such that there exist distinct verticesα, β∈V withα≈β. We will show this relation must be universal, and thus thatis a primitive digraph.

LetT be the block-cut-vertex tree of, letγ∈V be the vertex in the geodesic [α, β]T such thatd_T(β, γ )=2, and letbe the lobe ofcontainingβ andγ.

By Lemma 3.1the group (Aut)_{} acts primitively and not regularly on the lobe. Thus there exits an automorphismh∈(Aut)_{γ ,{}} which does not fixβ. By restricting the action of h to the vertices of , we see that there must be an element in Aut_γ which does not fix β. By Lemma 3.1, the subgroup of Aut induced by(Aut)_α,{}is equal to(Aut)_γ, so there must therefore exist an element g∈(Aut)_{α,γ ,{}}that does not fixβ.

Thus,β andβ^gare distinct vertices in. Nowα≈β, soα≈β^g, and therefore β≈β^g. Since(Aut)_{}is primitive onV and≈induces a non-trivial(Aut)_{}- congruence onV , this relation must be universal in. By assumption, Autacts transitively on the lobes of, so if two vertices lie in the same lobe then they must lie in the same congruence class. Thus, ifγ is any vertex of, andαx₁α₁x₂. . . x_nγ is the geodesic inT betweenαandγ, thenαandα₁lie in a common lobe, soα≈α₁. Similarly,α1≈α2andα2≈α3, soα≈α2andα≈α3. Continuing in this way we eventually obtainα≈γ. Hence, this congruence relation is universal onV .

Conversely, suppose the group Autacts primitively onV . Sinceis a primi- tive digraph with connectivity one, we can obtain an graphwith vertex setV and edge set{{α, β} |(α, β)∈A}. Two vertices are adjacent inif and only if they are adjacent in. As Autis primitive onV and Aut≤Aut, it follows that Aut must be primitive onV , and henceis a primitive graph. Sincehas connectivity one, the same is true of, so we may apply Theorem3.2to deduce the lobes of are primitive, pairwise isomorphic and each has at least three vertices. Now, given a lobeof, there is a lobe of such thatV =V . Therefore, the lobes ofhave at least three vertices, and are primitive but not automorphism-regular by Theorem2.6.

It remains to show they are pairwise isomorphic. Fix some lobeof and an arc(α, β)∈A. Let1be the digraph(V , (α, β)^Aut). As Autis primitive, this digraph is a connected subgraph of. Thus, every lobe ofmust contain an arc in A1. Furthermore, ifis a lobe of, then any automorphism ofmapping the arc (α, β)to an arc inmust mapto. Since₁is arc-transitive, the lobes ofmust

be pairwise isomorphic.

It is now a simple exercise to classify those vertex-transitive digraphs with connec- tivity one which are counterexamples to the application of Jung and Watkins’ result to digraphs without modification. Any such counterexample must be one of two types:

digraphs that satisfy the conditions of Jung and Watkins’ theorem, but are neverthe- less imprimitive; and digraphs that are primitive, but fail to satisfy Jung and Watkins’

characterisation.

Since the conditions given in Theorem3.3 under which one may be certain a vertex-transitive digraph with connectivity one is primitive include the corresponding conditions given in Jung and Watkins’ theorem, no primitive digraph with connectiv- ity one is of the latter type. Thus, any counterexample must be imprimitive, yet still satisfy the conditions of Jung and Watkins result. We begin with a lemma.

Lemma 3.4 For each primep, a digraphonpvertices is a directed cycle if and only if its automorphism group is the cyclic groupC_pof orderp.

Proof Supposepis prime andis a digraph onpvertices. Ifis a directed cycle then clearly its automorphism group isC_p.

Conversely, supposehas automorphism groupC_p. Without loss of generality, we may label the vertices ofas integers 0,1, . . . , p−1 such that(0,1)is an arc in andC_pis generated by the permutationρwith

i^ρ=i+1 modp.

SinceC_pis transitive onV , for some setJ⊆ {1, . . . , p−1}we may write A=

j∈J

(0, j )^Cp.

Note that 1∈J. Let σ be a permutation of V fixing the vertex 0 and fixingJ setwise. Choose(a, b)∈Aand observe(a, b)=(0, j )^ρk for somej∈J and some integer k. Now (a, b)^ρ−kσ =(0, j )^σ =(0, j) for somej∈J, and (0, j)∈A.

Thusσ lies in Autand, ifJ contains at least two elements, is not inC_p. Whence,

J= {1}andis a directed cycle.

Recall that any counterexample to the unmodified extension of Jung and Watkins’

result to digraphs must be imprimitive, yet still satisfy the conditions of their theorem.

By Theorem3.3, all such digraphs must have automorphism-regular primitive lobes which are pairwise isomorphic, with each possessing at least three vertices. Letbe such a digraph.

Ifis a lobe of, then Theorem1.1tells us that Autis cyclic of prime orderp.

Since this group is transitive, it implies thatmust have preciselypvertices. Thus is ap-vertex digraph whose automorphism group is the cyclic groupCp of order p, and is necessarily a directed cycle by Lemma3.4.

Conversely, we note that for any odd primep, a vertex-transitive digraph with connectivity one whose lobes havepvertices and automorphism groupC_p, satisfies the primitivity conditions given by Jung and Watkins for graphs.

Thus the counterexamples to the unmodified extension of Jung and Watkins’ result are precisely those digraphs whose lobes have an odd primep number of vertices, and are directed cycles. This is summarised in our concluding theorem. Here the undirected graph associated with the digraphis the graph with vertex setV and edge set{{α, β} |(α, β)∈Aor(β, α)∈A}.

Theorem 3.5 Ifis a vertex-transitive imprimitive digraph with connectivity one, then its associated (undirected) graph is primitive if and only if the lobes ofare pairwise isomorphic directedp-cycles, for some odd primep.

Acknowledgements This paper contains parts taken from the author’s DPhil thesis, completed under the supervision of Peter Neumann at the University of Oxford. The author would like to thank Dr Neumann for his tireless enthusiasm and helpful suggestions. The author would also like to thank the EPSRC for generously funding this research, and the two referees who strengthened this paper with their advice.

References

1. Bhattacharjee, M., Macpherson, D., Möller, R.G., Neumann, P.M.: Notes on Infinite Permutation Groups. Lecture Notes in Mathematics, vol. 1698. Springer, Berlin (1998)

2. Imrich, W.: Graphen mit transitiver Automorphismengruppe. Monatsh. Math. 73, 341–347 (1969) 3. Jung, H.A., Watkins, M.E.: On the structure of infinite vertex-transitive graphs. Discrete Math. 18,

45–53 (1977)