ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 11 (2016) 127-146 Two-arc-transitive two-valent digraphs of certain orders Katja Berčič IAM, University of Primorska, Muzejski trg 2, SI-6000 Koper, Slovenia Primož Potočnik * Faculty ofMathematics and Physics, University ofLjubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia, IAM, University of Primorska, Muzejski trg 2, SI-6000 Koper, Slovenia IMFM, Jadranska 19, SI-1000 Ljubljana, Slovenia Received 17 October 2014, accepted 15 December 2014, published online 1 October 2015 The topic of this paper is digraphs of in-valence and out-valence 2 that admit a 2-arc-transitive group of automorphisms. We classify such digraphs that satisfy certain additional conditions on their order. In particular, a classification of those with order kp or kp2 where k < 14 and p is a prime can be deduced from the results of this paper. Keywords: Graph, digraph, arc-transitive, order. Math. Subj. Class.: 05E18, 20B25 1 Introduction This paper is about finite connected arc-transitive digraphs of in- and out-valence 2 the order of which has a specific prime factorisation. We refer the reader to Section 2.1 for exact definitions of notions such as digraph, arc-transitive, valence etc. To simplify exposition, we tacitly assume throughout the paper (even where not stated explicitly) that all digraphs are finite and connected. Studying arc-transitive graphs and digraphs of orders with a specific prime factorisation has a long history and has become increasingly popular in the last decade or two. For example, arc-transitive graphs and digraphs of order p or 2p, where p is a prime, were classified in [3] and [4], respectively; later, using the classification of finite simple groups, all arc-transitive graphs and digraphs of order a product of two distinct primes were characterised * Supported in part by Slovenian Research Agency, projects L1-4292, J1-5433, J1-6720, and P1-0294. E-mail addresses: katja.bercic@upr.si (Katja Bercic), primoz.potocnik@fmf.uni-lj.si (Primož Potočnik) Abstract charchar This work is licensed under http://creativecommons.Org/licenses/by/3.0/ 128 Ars Math. Contemp. 11 (2016) 147-156 in [36], and independently in [26], and those that are 2-arc-transitive were determined in [23]. Once the prime factorisation of the order becomes more complex, results of this type become considerably more complicated (see [38] for an illustration of the difficulties that can arise when the order is a product of three distinct primes). However, when one fixes the valence (and perhaps imposes some further restrictions), further analysis becomes possible (see for example [5, 8, 10]). Since every connected digraph of valence 1 is isomorphic to a directed cycle, valence 2 is the smallest interesting valence in the context of arc-transitive digraphs. In the literature, arc-transitive 2-valent digraphs often arise in disguise as undirected 4-valent graphs admitting a group of automorphisms acting transitively on the edges, vertices, but not on the arcs of the graph; such group actions are usually called 2-arc-transitive. Namely, if r is a G-arc-transitive 2-valent digraph, then its underlying (undirected) graph r' admits a 2 -arc-transitive action of the group G; and conversely, if the automorphism group of an undirected 4-valent graph r' contains a subgroup G acting 2-arc-transitively on r', then there exists an orientation of the edges of r' that gives rise to a G-arc-transitive 2-valent digraph whose underlying graph is r' (in fact, there are precisely two such orientations giving rise to a pair of opposite digraphs). In this sense, the study of G-arc-transitive 2-valent digraphs is equivalent to the study of (G, 1)-arc-transitive graphs of valence 4. There is a substantial literature about the latter class of graphs (see for example [6, 18, 19, 20, 21, 25, 39, 40]). If r is an arc-transitive 2-valent digraph, then, for some positive integer s, the automorphism group Aut(r) acts regularly on the set of all s-arcs of the digraph. If s = 1, then the automorphism group acts regularly on the arc-set, and if the order of the digraph has a simple prime factorisation, one is usually able to classify all possible automorphism groups and use this information to determine all digraphs upon which such groups can act. An instructive example of how this can be done (in the case of undirected 4-valent graphs) can be found in [10]. Here, we will avoid this case and restrict ourselves to the case s > 2; that is, we will assume that our digraphs are all 2-arc-transitive. The two main results of the paper are Theorems 1.1 and 1.2, stated below and proved in Section 3. The digraphs P)X(M) appearing in the statements are defined in Section 2.5. Theorem 1.1. Let p and q be distinct odd primes, and let a, b, c be integers satisfying a e {0,1,2,3}, b, c € {0,1,2}, and (b,c) = (2,2). If r is a connected (G, 2)-arc-transitive 2-valent digraph of order 2aqbpc and G is non-solvable, then the order of r is at most 1224 and r is isomorphic to one of the sixty-seven digraphs in Table 1. Remark. Exact descriptions of the sixty-seven exceptional digraphs of Theorem 1.1 are available in [29] (for the digraphs of order up to 1000) and [1] (for digraphs of larger order). The digraphs are given there in a form readable by Magma [2]. Theorem 1.2. Let r be a connected (G, 2)-arc-transitive 2-valent digraph and suppose that G is solvable. Let n be the order of r, and suppose that one of the following holds: (i) n is odd and cube-free; (ii) n = 2am, where a € {1, 2, 3} and m is an odd, square-free integer; (iii) n = 2aqbp2, where a € {1, 2,3}, b e {0,1} and p, q are distinct odd primes. Then one of the following conclusions holds: K. Berčič and P. Potočnik: Two-arc-transitive two-valent digraphs of certain orders 129 Order | Name | | Autv | | |S| | soc(Aut) 2 - 3 - 5 ATD[30;6] 4 1 Alt(5) 2 - 3 - 7 ATD[42;3] 8 1 PSL(2, 7) 22 - 3 - 5 ATD[60;16] 4 1 Alt(5) X C2 22 - 3 - 7 ATD[84;20] 8 1 PSL(2, 7) X C2 22 - 3 - 7 ATD[84;23] 4 1 PSL(2, 7) 22 - 3 - 7 ATD[84;24] 4 1 PSL(2, 7) 2 - 32 - 5 ATD[90;12] 4 1 Alt(5) X C 3 2 - 32 - 5 ATD[90;13] 16 Alt(6) 23 - 3 - 5 ATD[120;11] 4 1 Alt(5) X C2 23 - 3 - 5 ATD[120;54] 4 1 Alt(5) X C2 23 - 3 - 5 ATD[120;56] 4 1 Alt(5) X C2 2 - 32 - 7 ATD[126;15] 8 1 PSL(2, 7) X C3 2 - 3 - 52 ATD[150;16] 4 1 Alt(5) X C 5 23 - 3 - 7 ATD[168;53] 8 1 PSL(2, 7) X C2 23 - 3 - 7 ATD[168;64] 4 1 PSL(2, 7) X C2 23 - 3 - 7 ATD[168;65] 4 1 PSL(2, 7) X C2 23 - 3 - 7 ATD[168;81] 4 1 PSL(2, 7) X C2 23 - 3 - 7 ATD[168;82] 4 1 PSL(2, 7) X C2 22 - 32 - 5 ATD[180;42] 4 1 Alt(6) 22 - 32 - 5 ATD[180;45] 4 1 Alt(5) X C2 X C3 22 ATD[180;57] 8 3 Alt(6) 22 ATD[180;58] 16 3 Alt(6) X C2 22 - 32 - 7 ATD[252;59] 8 1 PSL(2, 7) X C2 X C3 22 - 32 - 7 ATD[252;69] 4 1 PSL(2, 7) X C3 22 - 32 - 7 ATD[252;70] 4 1 PSL(2, 7) X C3 2 - 3 - 72 ATD[294;19] 8 1 PSL(2, 7) X C7 22 - 3 - 52 ATD[300;66] 4 1 Alt(5) X C2 X C5 2 - 32 - 17 ATD[306;11] 8 1 PSL(2, 17) 23 - 32 - 5 ATD[360;146] 4 1 Alt(6) X C2 23 - 32 - 5 ATD[360;148] 4 1 Alt(6) 23 - 32 - 5 ATD[360;150] 8 3 Alt(6) X C2 23 - 32 - 5 ATD[360;153] 8 3 Alt(6) X C2 23 - 32 - 5 ATD[360;154] 4 1 Alt(6) 23 - 32 - 5 ATD[360;158] 4 1 Alt(5) X C2 23 - 32 - 5 ATD[360;163] 4 1 Alt(5) X C2 X C3 23 - 32 - 5 ATD[360;172] 4 1 Alt(5) X C2 X C3 23 - 32 - 5 ATD[360;174] 4 1 Alt(5) X C2 X C3 23 - 32 - 5 ATD[360;201] 8 3 Alt(6) X C2 23 - 32 - 5 ATD[360;202] 16 3 Alt(6) X C2 23 - 32 - 7 ATD[504;162] 8 1 PSL(2, 7) X C2 X C3 23 - 32 - 7 ATD[504;180] 4 1 PSL(2, 7) X C2 X C3 23 - 32 - 7 ATD[504;182] 4 1 PSL(2, 7) X C2 X C3 23 - 32 - 7 ATD[504;232] 4 1 PSL(2, 7) X C2 X C3 23 - 32 - 7 ATD[504;233] 4 1 PSL(2, 7) X C2 X C3 22 - 3 - 72 ATD[588;87] 8 1 PSL(2, 7) X C2 X C7 22 - 3 - 72 ATD[588;90] 4 1 PSL(2, 7) X C7 22 - 3 - 72 ATD[588;91] 4 1 PSL(2, 7) X C7 23 - 3 - 52 ATD[600;199] 4 1 Alt(5) X C2 X C5 23 - 3 - 52 ATD[600;201] 4 1 Alt(5) X C2 X C5 23 - 3 - 52 ATD[600;204] 4 1 Alt(5) X C2 X C5 22 - 32 - 17 ATD[612;48] 4 1 PSL(2, 17) 22 - 32 - 17 ATD[612;49] 8 1 PSL(2, 17) 23 - 3 - 72 X1 4 1 PSL(2, 7) X C2 X C7 23 - 3 - 72 X2 4 1 PSL(2, 7) X C2 X C7 23 - 3 - 72 X3 4 1 PSL(2, 7) X C2 X C7 23 - 3 - 72 X4 4 1 PSL(2, 7) X C2 X C7 23 - 3 - 72 X5 8 1 PSL(2, 7) X C2 X C7 23 - 32 - 17 X6 4 1 PSL(2, 17) X C2 23 - 32 - 17 X7 8 1 PSL(2, 17) X C2 23 - 32 - 17 X8 4 1 PSL(2, 17) X C2 23 - 32 - 17 X9 4 1 PSL(2, 17) X C2 22 - 32 - 17 X10 4 1 PSL(2, 17) 22 - 32 - 17 X11 4 1 PSL(2, 17) 22 - 32 - 17 X12 4 1 PSL(2, 17) 22 - 32 - 17 X13 4 1 PSL(2, 17) 22 - 32 - 17 X14 4 1 PSL(2, 17) 22 - 32 - 17 X15 4 1 PSL(2, 17) Table 1: Exceptional digraphs for Theorem 1.1. The column "Name" refers to the digraph names as given in [28] (up to order 1000) or [1] (for orders greater than 1000). The number of non-solvable 2-arc-transitive subgroups of Aut(T) (up to conjugacy) is given in the column called |S |. 130 Ars Math. Contemp. 11 (2016) 147-156 (a) r = pt( t, s) for some t > 1 and s > 0; (b) condition (iii) holds, G has a normal Sylow p-subgroup P, which is elementary abelian of order p2, and r/p = pX( t, s) for some t > 1 and s > 0. Remark. Let us spend a few words on the seemingly unfinished case (b) of Theorem 1.2. The digraphs appearing in this case arise from regular covering projections onto the digraphs PX(t, s) of order 2aqb where the groups of covering transformations are elementary abelian of order p2, along which a 2-arc-transitive group of automorphisms of pX(t, s) lifts. The theory of lifting groups along elementary abelian covering projections was developed in [14] and illustrated in several papers (see for example [15, 31]). If desired, one could use this theory to determine all the resulting covering digraphs for fixed (a, q, b). In particular, we could easily obtain a complete classification in the case of order kp or kp2 for every k < 14 and prime p. Recently, numerous papers have been written in which authors classified arc-transitive graphs and digraphs of fixed valence and orders with a simple prime factorisation (usually kp or kp2 for a fixed small k and variable prime p). Unlike in many of the above mentioned papers, we have tried to prove our results in as general a form as our approach allowed. Slight improvements are certainly possible (for example, using the classification of finite simple groups whose order is divisible by four primes only [13], one could extend Theorem 1.1 to orders divisible by a third odd prime). However, it seems that major improvements would require new ideas. Finally, we would like to thank Pablo Spiga for pointing out an oversight in a draft version of the paper, to Rok Pozar for independent computer-based confirmation of Theorem 1.1 in the range on up to 1500 vertices, and to the anonymous referees for their most helpful remarks and for prompt and careful reading of the paper. 2 Preliminaries 2.1 On graphs and digraphs Even though we are mainly interested in simple digraphs, it will be convenient in the proofs to allow digraphs to be non-simple. We therefore define a digraph r as a quadruple (V, A, head, tail) where V and A are finite non-empty sets and head and tail are functions mapping from A to V; we call the sets V and A the vertex-set and the arc-set of r and denote them by V(r) and A(r), respectively. We then think of an arc to point from its tail to its head. The cardinality of V(r) is called the order of r. Similarly, a graph r is determined by a vertex-set V(r), edge-set E(r) and a function end: E(r) ^ {X C V(r) : |X| € {1, 2}}, assigning a pair of endvertices to each edge of r. An edge e of a graph r is a loop provided that | end(e) | = 1, and two edges y and x are parallel if end(x) = end(y). A graph r without loops and parallel edges is simple and is uniquely determined by V(r) and the set {end(e) : e € E(r)}. If r is a digraph, then the underlying graph of r is the graph with vertex-set V(r), edge-set A(r) and the end-function defined by end(x) = {tail(x), head(x)}. A digraph is simple provided that its underlying graph is simple. A sequence (xi,..., xs) of arcs of a digraph r is called an s-arc of r provided that head(xj) = tail(xi+1) for every i € {1,..., s - 1}. The set of all s-arcs of r is denoted by As(r). K. Berčič and P. Potočnik: Two-arc-transitive two-valent digraphs of certain orders 131 An automorphism of a digraph r is a permutation of V(T) U A(T) that preserves V(T) set-wise and commutes with the functions head and tail. If G is a subgroup of the automorphism group Aut(r), then r is said to be G-arc-transitive (or (G, s)-arc-transitive) provided that G acts transitively on A(r) (or As(r), respectively). When G = Aut(r), the symbol G can be omitted from this notation. If v is the tail and u the head of some arc x, then we say that u is an out-neighbour of v and v an in-neighbour of u. For a vertex v G V(r), we let r+(v) = {x G A(r) : tail(x) = v} and r- (v) = {x G A(r) : head(x) = v}, and call the sizes of these two sets the out-valence and the in-valence of v in r, respectively. (Note that when the digraph is not simple the out-valence does not necessarily equal the number of out-neighbours of v, and similarly for the in-valence). If for some integer k, the in-valence (out-valence) of every vertex equals k, then we say that the digraph has in-valence (out-valence, respectively) k. A digraph is called k-valent if it is of out-valence and in-valence k. Observe that every arc-transitive digraph without vertices of out-valence 0 (in particular, every connected arc-transitive digraph) is vertex-transitive. 2.2 Non-simple arc-transitive 2-valent digraphs In this section, we characterise arc-transitive 2-valent digraphs that are not simple. To formulate the characterisation (Lemma 2.1), we first need to introduce the digraphs 3 and tC?n for n > 1. Both digraphs arise from an undirected cycle with each edge doubled, and their vertex-sets and arc-sets can be taken to be Zn and Zn x Z2, respectively. In 3n ) the functions head and tail are defined with tail(i, e) = i and head(i, e) = i + 1 for every arc (i, e) G Zn x Z2. Similarly, in 3n, the functions head and tail are defined with tail(i, 0) = i, head(i, 0) = i +1, tail(i, 1) = i + 1, and head(i, 1) = i. Note that 312) and 3 1 are both isomorphic to a digraph with a single vertex and two directed loops attached to it, while 322) and tc?2 consist of two vertices and four arcs between them, two pointing in each of the two possible directions. The proof of the following lemma is straightforward and is left to the reader. Lemma 2.1. If r is a connected non-simple arc-transitive 2-valent digraph of order n, then r = 3n2) or r = 3n, and if in addition r is 2-arc-transitive, then r = 3n2) for some n > 2. The following result will be needed in the proof of Theorem 1.2. Lemma 2.2. Let G be a subgroup of Aut(3 n2) ) acting transitively on the s-arcs but not on the (s + 1)-arcs of3n2) and let v be a vertex of3n2). Then Gv is an elementary abelian 2-group of order 2s and is normal in G. If Gv has order 4 and contains a non-trivial central element of G, then n is even. Proof. Observe that every automorphism of 3n2) that fixes v fixes every vertex of 3n2), implying that Gv is the kernel of the action of G on the vertex-set of 3n , and is therefore normal in G. Furthermore, Gv preserves set-wise each pair of arcs with the same tail (and thus the same head). In particular, Gv is an elementary abelian 2-group. Since G is transitive on the s-arcs but not on the (s + 1)-arcs, it is an easy exercise to show that Gv acts regularly on the s-arcs starting at v, and since there are 2s of them, it follows that |Gv | = 2s. 132 Ars Math. Contemp. 11 (2016) 147-156 Suppose now that n is odd, that |Gv | = 4, and that t is a non-trivial central element of G contained in Gv. Without loss of generality, we may assume that t acts non-trivially on the pair of arcs pointing out of v. Furthermore, since the index of Gv in G is n, it follows that Gv is the unique Sylow 2-subgroup of G, and thus G = Gv x H, where H is a group of order n. Moreover, since Gv is the kernel of the action of G on the vertices of (ti2), it follows that H acts regularly on the vertices of (ti2); in particular, H = (g) where g is an automorphism of order n that maps every vertex to its unique out-neighbour. Since t = tg, the element t acts non-trivially on every pair of arcs sharing the same tail. In particular, t is the unique non-trivial central element of G contained in Gv. Since G = Gv H and since Gv is abelian, this shows that H centralises no element of Gv \ {1, t }. However, this is impossible since H has odd order and | Gv \{ 1, t}| = 2. This contradiction completes the proof of the lemma. □ 2.3 Alter-relations, alter-exponent, radius and perimeter In this section, we present a very useful tool for studying digraphs, based on the orientation of arcs in the walks of a digraph. The concepts presented in this section were first introduced in [24] (for a generalisation to infinite digraphs, see [16]). All the facts stated below were proved in [24] for simple digraphs and extend without any change to digraphs with loops and multiple arcs. A walk from a vertex v0 to a vertex vs of length s in a digraph r is a sequence (vo,xi, vi,..., vs_i, xs, vs) of arcs xj G A(r) and vertices v j G V(r) such that for any i G {1,..., s} the pair (tail(xj), head(xj)) equals either (vi_1, vj) or (vj, vi_1). In the former case, we say that xj is positively oriented, while in the latter case we say that xj is negatively oriented in the walk. A walk is directed if all of its arcs are positively oriented and is alternating if the orientation of the arcs in the walk alternates. A digraph r is (strongly) connected provided that for any two vertices u, v G r there exists a (directed) walk from u to v. A vertex-transitive digraph is strongly connected if and only if it is connected (see, for example, [27, Lemma 2]). A walk is closed provided that it begins and ends in the same vertex. Let W = (v0, x1, v1, x2,..., xn, vn) be a walk in a digraph r. The sum s(W) is the difference between the number of positively oriented arcs in W and the number of negatively oriented arcs in W. The k-th partial sum sk (W) is defined as the sum of the initial walk (v0, x1, v1,..., vk) of length k. The set {sk (W), 0 < k < n} is the tolerance of W and vertices u and v are alter-equivalent with tolerance J (written uAjv) if there exists a walk from u to v with sum 0 and tolerance contained in J. It transpires that A j is an equivalence relation (called an alter-relation) for every interval J containing 0 and that it is invariant under every automorphism of r. We will denote the equivalence class containing a vertex v with Aj(v) and use the shorthand Aj(v) to mean A[0 j](v) (when i > 0) or A[j 0](v) (when i < 0). Note that since r is a finite digraph, there exists a non-negative integer e such that Ae = Ae+1 and (by induction) Ae = ATO. The smallest such integer e is called the alter-exponent of r and denoted exp(r). It can be shown that exp(r) also equals the smallest non-negative integer i for which A_j = A_j_1 as well as the smallest i such that A[_j j] = A[_j_1j+1]. When we consider alter-relations in several different digraphs, we shall use the symbol AJ (instead of A j ) to denote the one in the digraph r. The number of equivalence classes of the alter-relation is called the perimeter of K. Berčič and P. Potočnik: Two-arc-transitive two-valent digraphs of certain orders 133 r and denoted perim(r). If the in-valence and the out-valence of each vertex is positive, then the equivalence classes Bi of can be indexed by Zp (where p = perim(r)) in such a way that every arc of r having its tail in Bi, has its head in Bi+1. We will be particularly interested in the sets A1(v) and A_1(v). Note that these sets consists of precisely those vertices that can be reached from v by alternating walks of even length starting with a positively (negatively, respectively) oriented arc. The intersection A1(v) n A_1(v) will be denoted Att(v) and called the attachment set (at vertex v). Suppose henceforth that r is a G-arc-transitive digraph. Then the sets Aj (v) (as well as Att(v)) are all blocks for the action of G on V(r) and their size depends only on J (but not on v). One can thus define the radius of r (denoted rad(r)) to be the cardinality of |A1(v)| for any v G r, and the attachment number of r (denoted att(r)) to be the cardinality of Att(v) for any v G V(r). Since Att(v) C A1(v) C A2(v) C ..., we see that att(r) divides rad(r), and that |Ai(v)| divides |Ai+1(v)| for every i > 1. Suppose now that r is a 2-valent arc-transitive digraph. Then the sub-digraph of r induced by a closed alternating walk of sum 0 that traverses every arc of r at most once is called an alternating cycle. The length of an alternating cycle is defined to be the length of the closed alternating walk that induces it. (Alternating cycles were introduced in [19] in the context of simple (G, 1 )-arc-transitive 4-valent graphs.) Note that an alternating cycle is uniquely determined by any of its arcs, implying that the set of alternating cycles induces a decomposition of the arc-set of r. Furthermore, this decomposition is preserved by every automorphism of r, implying that all alternating cycles in r have the same length. In addition to the assumption that r is a 2-valent arc-transitive digraph, assume for the rest of the section that r is not isomorphic to any tC?n with n odd. Then an alternating cycle is indeed a cycle (in the sense that the walk that generates it traverses every vertex of the digraph at most once), and r contains at least two alternating cycles. Furthermore, observe that A1 (v) consists of every second vertex of an alternating cycle starting with a positively oriented arc with its tail in v, and similarly, A_1(v) consist of every second vertex of an alternating cycle starting with a negatively oriented arc with its head in v. In particular, |A1(v)| = |A_1(v)| and the length of each alternating cycle is twice the radius of r. Note also that there are precisely two alternating cycles meeting in a given vertex v and the set of vertices that are contained in both of these alternating cycles is precisely Att(v). Two alternating cycles therefore meet in either 0 or att(r) vertices. Suppose now that att(r) > 3 and let g G Aut(r) fix an arc x of r. Then g fixes point-wise the alternating cycle C containing x. Since att(r) > 3, g fixes also at least three vertices of each alternating cycle intersecting C, and therefore fixes each of these cycles point-wise. But then by connectivity, g fixes each alternating cycles of r point-wise. In particular, g is trivial. This proves the following easy, but very useful result. Lemma 2.3. If r is a connected 2-valent 2-arc-transitive digraph, then att(r) < 2. We finish this section with another useful result. Lemma 2.4. If r is a connected 2-valent 2-arc-transitive digraph and exp(r) = 1, then r = rX( m, 1) for some integer m. Proof. If r is not simple, then by Lemma 2.1, r = cCn2) for some n > 2, implying that exp(r) = 0; a contradiction. Hence r is simple, and we can apply [30, Theorem 7.1] to 134 Ars Math. Contemp. 11 (2016) 147-156 conclude that rad(T) = 2. Since exp(T) = 1, it is then easy to see that att(T) = 2, and also that r m, 1) for some m (see, for example, [19, Proposition 3.1]). □ 2.4 Covers and quotients The second tool that we will use extensively is the concept of (di)graph coverings. This tool is usually defined in the setting of undirected graphs, but extends naturally to digraphs. In this section, we present a few basic facts and results and refer the reader to [14, 17] for more details. Let r and A be two digraphs. A morphism from r onto A is a function f : V(r) U A(A) ^ V(A) U A(A) mapping V(r) to V(A) and A(r) to A(A) such that f (tail(x)) = tail(f (x)) and f (head(x)) = head(f (x)) for every x G A(r). A morphism is an epimorphism or isomorphism if it is surjective or bijective, respectively. (Note that an automorphism of a digraph is precisely an isomorphism from the digraph onto itself.) An epimorphism p: r ^ A is a covering projection provided that for every v G V(r) the restrictions p+ : r+(v) ^ A+(p(v)) and p- : r-(v) ^ A-(p(v)) of p to the out-and in-neighbourhoods of v are bijective. For simplicity, we shall also require both r and A to be connected. The preimage p-1 (x) of a vertex or an arc x of A is called a fibre of the covering projection p and the group of all automorphisms of r that preserve each fibre set-wise is called the group of covering transformations. If the latter is transitive on each fibre, then the covering projection is regular. Normal quotients of simple graphs were introduced in [33, 34] and have now become a standard tool in studying symmetric graphs. Here we adapt this concept slightly to fit into the setting of digraphs admitting loops and multiple arcs. This adaptation will prove most useful in the proofs of our main results. Let r be a digraph and let N < Aut(r). Let An = {xN : x G A(r)} and VN = {vN : v G V(r)} denote the sets of N-orbits on the arcs and vertices of r, respectively. Further, let tailN: AN ^ VN and headN: AN ^ VN be defined by tailN(xN) = tail(x)N and headN(xN) = head(x)N. This defines the quotient digraph r/N = (VN, An, headN, tailN), together with the obvious epimorphism pN: r ^ r/N satisfying pN (x) = xN for every x G V(r) U A(r), called the normal quotient projection relative to N .If N G < Aut(r), then there is an obvious, but not necessarily faithful action of the quotient group g/n on the digraph r/N. Note also that if G acts transitively on vertices, arcs or s-arcs of r, then so does g/n on r/N. If the quotient projection pN is a covering projection, then the situation is particularly nice; for example: Lemma 2.5. Let r be a digraph, let G < Aut(r) and let N be a normal subgroup of G. If the quotient projection p: r ^ r/N is a covering projection, then the action of g/n on V(f/n) U A(r/N) is faithful, and moreover, the stabilisers Gv and (g/n)vn are isomorphic for every v G V(r). We say in this case that the group g/n lifts along p. More precisely, a group H < Aut(r/N) lifts along p if there exists some G < Aut(r), containing N as a normal subgroup, such that g/n = H. We now state two very useful sufficient and necessary conditions for a normal quotient projection to be a regular covering projection. (We shall call a group N of automorphisms of r semiregular provided that the stabiliser Nv is trivial for every v G V(r).) K. Berčič and P. Potočnik: Two-arc-transitive two-valent digraphs of certain orders 135 Lemma 2.6. Let r be a connected digraph, let N < Aut(T) and let p: r ^ r/N be the corresponding quotient projection. Then the following statements are equivalent: (a) N is semiregular; (b) the in-valence as well as the out-valence of v and p(v) coincide for every v G V (T); (c) p is a regular covering projection. The rest of the section is devoted to the interplay between the concepts of alter-relations and covering projections. Lemma 2.7. Let p: r ^ A be a covering projection, let v be a vertex of r and let J be an interval of integers containing 0. Then p(A^ (v)) = Aj- (p(v)). Proof. Suppose that u G p(AJ(v)). Then there exists u G V(r) such that p(u) = u and a walk (v, xi, vi,..., xn, u) in r of sum 0 and tolerance within J. But then the projected walk (p(v), p(x1), p(v1), ..., p(xn), u) is also a walk of sum 0 and tolerance within J, implying that u G Aj-(p(v)). Conversely, suppose that u G Aj-(p(v)). Then there exists a walk (p(v), x1, -y1, ..., xn, u) of sum 0 and tolerance within J. Since p is a local bijection, one can then construct a lift (v, x1, v1, ..., xn, u) such that p(xj) = x4, p(vj) = v4, and p(u) = u. Note that this lift will also have sum 0 and tolerance within J, implying that u G A J (v), and therefore u G p(Aj(v)). □ Lemma 2.8. Let r be a G-vertex-transitive digraph, let N be a semiregular normal subgroup of G, let A = r/w and let p: r ^ A be the corresponding covering projection. Further, let v be a vertex of r, and let J be an interval of integers containing 0. Then |AJ(v)| divides |N||AJ(p(v))|. Proof. In view of Lemma 2.7, we see that AJ (v) C p-1(p(Aj (v))) = p-1(A^ (p(v))). Since Aj- (p(v)) is a block for the action of g/n on A, it follows easily that p-1(Aj (p(v))) is a block for the action of G on r. Since A J (v) is also a block for G, it follows that |AJ(v)| divides |p-1(A^(p(v)))|. However, since the p-preimage of a vertex in A is an N-orbit on r, it follows that the latter equals |N || A J (p(v)) |. □ Lemma 2.9. Let r be a connected, (G, 2)-arc-transitive 2-valent digraph and let N be a normal subgroup of G. If N has odd prime order, then rad(r/N) = rad(r). Proof. Let q be the order of N, let A = r/N and let p: r ^ A be the corresponding quotient projection. Suppose that the conclusion of the lemma is false, that is, rad(r/N) = rad(r). Since Gv is a 2-group (see Lemma 3.1) and N is of odd order, N acts semiregularly on V(r). By Lemma 2.6, the quotient projection p is then a regular covering projection. Choose a vertex v of r and e G {-1,1}, and consider the set T = A^(v). Recall that |T| = rad(r). By Lemma 2.7, p(T) = A^(p(v)). Since the size of the latter is rad(A), it follows by our initial assumption that | p(T) | = |T|, implying that T contains at least two elements of the orbit vN. Since both T and vN are blocks for the action of G on V(r), so is their intersection. However, vN is of prime size, implying that vN = vN n T, and thus vN C T. Since this is true for any choice of e, it follows that vN C Ar(v) n Ar1(v) = Att(v). But then by Lemma 2.3 it follows that r is not 2-arc-transitive, a contradiction. □ 136 Ars Math. Contemp. 11 (2016) 147-156 2.5 Partial line graphs and digraphs of Praeger and Xu In this section, we give a brief overview of the very useful concept of partial line graph construction, which was invented in [21] to analyse G-arc-transitive 2-valent digraphs of radius 2, and was further developed in [30]. For a digraph r and a positive integer s, the s-th partial line graph Pls(r) of r is the digraph with vertex-set being the set of s-arcs As(r), the arc-set being As+1(r), and the functions tail and head defined by the rules tail(x1,..., xs+1) = (x1,..., xs) and head(x1,..., xs+1) = (x2,..., xs+1) for every (s + 1)-arc (x1,..., xs+1) of r. Moreover, we let Plo(r) = r and write Pl instead of Pl1. Note that if r is a 2-valent digraph, then so is Pls(r) for every s > 0. The following formula (which appeared as [30, Lemma 3.2(i)] in the context of simple digraphs), provides an alternative, recursive definition of the Pls operator: Pls(r) = Pl(Pls_1(r)) for s > 1. (2.1) The lemma below follows from [30, Lemma 3.1(iv)] and [30, Lemma 3.2(ii)] in the context of simple digraphs. The proof remains unchanged in the case of non-simple digraphs. Lemma 2.10. If r is a vertex-transitive digraph, then exp(Pl(r)) = exp(r) + 1. The following result appeared as [30, Lemma 5.1] in the context of simple digraphs, and extends to general digraphs via Lemma 2.1. Lemma 2.11. If r is a 2-valent (G, 2)-arc-transitive digraph such that rad(r) = 2, then r = Pl(A), where A is a 2-valent (G, 3)-arc-transitive digraph of order half that of r. The Pl operator can be used to define a very important class of digraphs, first studied by Praeger and Xu [37] in the context of simple graphs, and by Praeger [35] in the context of simple digraphs. For integers n and s, n > 1, s > 0, let -3(ns) ( 3 n2) if s=o (n,s) \ Pl(P}X(n,s - 1)) if s > 1 (.) We shall call a graph isomorphic to some —)X(n, s) simply a -digraph. Note that, in view of (2.1), we have -)X(n,s) = Pls(3 n2)). (2.3) The automorphism group of 3i2) acts naturally as a group of automorphisms on each -3(n, s) for s > 1. The following surprising characterisation of -3 -digraphs was proved in [35, Theorem 2.9] in the context of simple digraphs. In view of Lemma 2.1, the result extends to non-simple digraphs. Lemma 2.12. Let r be a connected 2-valent G-arc-transitive digraph and let v e V(r). If G contains an abelian normal subgroup N that is not semiregular, then r is a -digraph. The following lemma is an analogue of a similar result for the undirected graphs (see [9, Lemma 3.1]). Our proof is just a slight modification of the proof given there. K. Berčič and P. Potočnik: Two-arc-transitive two-valent digraphs of certain orders 137 Lemma 2.13. Let r be a connected 2-valent, G-arc-transitive digraph and let N be a minimal normal subgroup of G. Suppose that N is a 2-group and that r/N = cCi2) for some n > 1. Then r is a -digraph. Proof. Since N is a minimal normal subgroup of G and a 2-group, it is elementary abelian. Let K be the kernel of the action of G on the set of N-orbits on V(r), and observe that G/K acts faithfully on V(r/N). Let C be the centraliser of N in K. Then N < C < K. Since N and K are normal in G, so is C. Since N and K have the same orbits on V(r), so does C, implying that K = NKv and C = NCv for any vertex v. Since the quotient r/N is 2-valent, Lemma 2.6 implies that the quotient projection r ^ r/N is a covering projection, and also that N is semiregular (for otherwise the valence of the quotient r/N would be less than that of r). Therefore, N n Cv < Nv = 1, and since Cv centralises N, we see that C = N x Cv. Since the quotient projection r ^ r/N is a covering projection, Lemma 2.5 implies that Gv embeds into a vertex-stabiliser in Aut( cC n2) ). In particular, Gv (and thus Cv) is an elementary abelian 2-group, implying that C is an abelian normal subgroup of G. Let us now show that Cv = 1. By way of contradiction, assume that Cv = 1, and thus that C = NCv = N. Now recall that K = NKv and N n Kv = 1. Since both N and Kv are 2-groups, so is K. In particular, the centre Z(K) is non-trivial. On the other hand, since Z(K) < C and since C = N, we see that Z(K) < N. Since N is a minimal normal subgroup of G, this implies that N = Z(K). But then K = NKv = N x Kv, and thus K is an elementary abelian 2-group. In particular, N, being the centre of K, equals K. Now recall that g/k acts faithfully on V(r/N). On the other hand, g/k equals g/n, which is clearly unfaithful on V(r/N). This contradiction shows that Cv = 1, and by Lemma 2.12, r is a -digraph, as claimed. □ Lemma 2.14. Let n and s be integers, n > 1, s > 0, let A = pX(n, s) and let v be a vertex of A. Then exp(A) = s, |A^(v)| = 2s and perim(A) = n. Suppose G is a group acting transitively on the arcs of A and let K = (Gu : u G V(A)), that is, the group generated by all the vertex-stabilisers in G. Then K is the kernel of the action of G on the partition |A^(u) : u G V(A)} and vK = A^(v); in particular, K is normal in G. Furthermore, the group K is elementary abelian of order 2s |Gv |, the quotient digraph a/k is isomorphic to a directed cycle of length n, and g/k is a cyclic group of order n. Proof. Observe first that exp(—)X(n, 0)) = exp( cC i2) ) = 0. On the other hand, by formula (2.2), A = Pl(p}X( n, s — 1)), and thus by induction and Lemma 2.10, exp(A) = s, as claimed. By formula (2.3), a vertex of A is an s-arc of cCi2). Now recall that V(cCi2)) = Zn and that there is an arc pointing from i to j if and only if j — i = 1. It is now clear that if v is an s-arc of cC!2) starting in a vertex i of cC!2), and W is a walk in A of sum k starting in v, then the end-point of W will be an s-arc of cC!2) starting in i + k; in particular, every member of A^(v) is one of the 2s s-arcs of cCi2) starting in i. On the other hand, if w and u are arbitrary s-arcs of cC!2) starting in i and i + s, respectively, then there clearly exists a directed walk in A of length s from v to u. By combining two such walks from v to u and from an arbitrary w to u, one gets a walk from v to w of sum 0. This shows that Aa (v) is precisely the set of all s-arcs of cC!2) starting in i. In particular, |Aa (v)| = 2s, 138 Ars Math. Contemp. 11 (2016) 147-156 as claimed. Since | V(A)| = 2sn and since perim(A) = | V(A)|/|A^(v)|, it follows that perim(A) = n. The equality vK = A^(v) follows directly from [30, Lemma 4.1] and [30, Corollary 4.2]. In particular, K fixes every class A^(u), u G A, set-wise, implying that K is contained in the kernel (call it M) of the action of G on the partition |A^(u) : u G V(A)}. Moreover, vK = vM, and since Kv = Gv = Mv, it follows that K = M .In particular, |K| = |vK| |Kv | = 2s|Gv |, as claimed. The fact that a/k is isomorphic to the directed cycle of length perim(A) and that g/k is a cyclic group of order perim(A) is now a direct consequence of either [24, Propositions 3.2 and 3.5] or [35, Proposition 2.1]. Finally, to see that K is elementary abelian, recall that a vertex of A is an s-arc in "J2), and thus the stabiliser of a vertex in Aut(A) equals the stabiliser of an s-arc in Aut( "ctJ2)). However, each stabiliser of an s-arc in Aut( "C J2)) is contained in the kernel of the action of Aut( 1000. Suppose that G acts transitively on the s-arcs but not on the (s + 1)-arcs of r. Then |Gv | = 2s (see Lemma 3.1) and therefore |G| = 2a+sqbpc. Now consider a composition series 1 = G0 Gi ... Gk = G of G, and the corresponding set of composition factors Fi = Gi/Gi-i for i e {1,..., k}. Recall that F are simple groups. Since G is non-solvable, there exists j e {1,..., k} such that Fj is non-abelian. Let T = Fj and note that |T| divides |G|, which equals 2a+sqbpc. It is known that there are precisely eight non-abelian simple groups whose orders are divisible by at most three distinct primes (see, for example, [12]); these are Alt(5), PSL(2,7), Alt(6), PSL(2, 8), PSL(2,17), PSL(3, 3), PSU(3,3), and PSU(4, 2). Out of these, only the first five are such that the odd primes appear with multiplicity at most 2; these five groups, together with their orders and the orders of their automorphism groups are listed in Table 2. 140 Ars Math. Contemp. 11 (2016) 147-156 T |T | | Aut(T)| Alt(5) 22 • 3 5 22 3 5 = 120 PSL(2, 7) 23 • 3 7 24 3 7 = 336 Alt(6) 23 • 32 5 25 32 5 = 1440 PSL(2, 8) 23 • 32 7 23 33 7 = 1512 PSL(2, 17) 24 • 32 17 25 • 32 • 17 = 4896 Table 2: Simple groups of orders divisible by three primes only, with odd part cube-free Observe that the order of each of these groups is divisible by 3 and that the other odd prime divisor is 5,7, or 17. We may thus assume without loss of generality that q = 3 and p e {5, 7,17}. If p = 5, then | V(T)| < 8 • 3 • 52 = 600, contradicting our initial assumption. This rules out the groups Alt(5) and Alt(6) as possibilities for T. If p = 7, then the order 2a3b7c of r is larger than 1000 only when a = 3, b = 1 and c =2. Since 9 divides the order of PSL(2,8), this implies that T ^ PSL(2,8), and therefore T = PSL(2,7) and |V(r)| = 8 • 3 • 72 = 1176. Finally, if p = 17, then T = PSL(2,17), and since 32 divides the order of PSL(2,17), it follows that the order of r is 8 • 32 • 17 = 1224. We shall now distinguish two cases, depending on whether G contains a non-trivial abelian normal subgroup or not. Case I. Suppose that G contains a non-trivial abelian normal subgroup. Then G contains a minimal normal subgroup N that is abelian. Since G is non-solvable, r is not isomorphic to a -digraph. In view of Lemma 2.12, N is then semiregular, and thus p: r X r/N is a regular covering projection. If N is a 2-group, then, since the 2-part of | V(r)| is 8, we see that |N| e {2,4,8}. The possible orders of r/N are then 147 and 153 (when |N| = 8, and T = PSL(2, 7) and PSL(2,17), respectively), 294 and 306 (when |N| = 4), and 588 and 612 (when |N| = 2). Now suppose that N is of odd order. Since N is solvable, T is a composition factor of g/n and thus |T| divides |G|/|N| = 2a+sqbpc/|N|. Since |N| is odd and b + c < 3, it follows that the odd part of |T | is of the form qb pc where b' + c' < 2; in particular, T ^ PSL(2,17), and therefore T = PSL(2, 7), |N| = 3 or |N| = 7, and | V(r/N)| = 2a • 3 • 7 < 168. In fact, since we have already established that | V(r) | = 8 • 3 • 72 when T ^ PSL(2,7), it follows that |N| = 7 and | V(f/n) | = 168. We have thus shown that in Case I, we have | V(f/n) | e {147,153,168, 294,306,588, 612} and therefore the quotient digraph r/N appears in the census [28]. By searching the census for 2-arc-transitive digraphs of these orders with a non-solvable automorphism group, one sees that the triple (T, |N|, r/N) is as one given in Table 3 (here the data in the last column corresponds to the names of digraphs as given in [28]). Using the methods described in, say, [14, 32], for each of the digraphs r/N from Table 3, all the corresponding N-regular covers were computed for which a 2-arc-transitive subgroup of Aut(r/N) lifts, and the resulting nine covering digraphs were included in Table 1 under the names Xi, X2,..., X9. Case II. Suppose now that G contains no non-trivial abelian normal subgroups. Let us now consider the group generated by all minimal normal subgroups of G, called the socle of G and denoted soc(G). Since G contains no non-trivial abelian normal subgroups, it K. Berčič and P. Potočnik: Two-arc-transitive two-valent digraphs of certain orders 141 T | N | r/n PSL(2, 7) 2 ATD[588;87], ATD[588;90], ATD[588;91] PSL(2, 7) 4 ATD[294;19] PSL(2, 7) 8 order 147; none PSL(2, 7) 7 ATD[168;53], ATD[168;64], ATD[168;65], ATD[168;81], ATD[168;82] PSL(2,17) 2 ATD[612;48], ATD[612;49] PSL(2,17) 4 ATD[306;11] PSL(2,17) 8 order 153; none Table 3: Possible quotients of r by a minimal abelian normal subgroup follows that soc(G) is a direct product of non-abelian simple groups (see, for example, [7, Theorem 4.3A]). Since the order of every non-abelian simple group is divisible by at least three distinct primes, and since not both b and c are 2, soc(G) is a simple normal subgroup of G and is therefore isomorphic to the non-abelian composition factor T of G. Moreover, G acts faithfully by conjugation on soc(G) and thus embeds into its automorphism group. Since soc(G) is isomorphic to either PSL(2,7) or PSL(2,17), we see that G is isomorphic to one of PSL(2, 7), PGL(2,7), PSL(2,17) or PGL(2,17). On the other hand, recall that |G| = 2a+sqbpa and that a = 3 and s > 2, implying that |G| is divisible by 25. This rules out all but the last possibility, that is G = PGL(2,17). Since, in this case, | V(r)| = 23 • 32 • 17 and |G| = 25 • 32 • 17, it follows that |Gv | = 4. By Lemma 3.1, Gv is elementary abelian. In particular, r is a coset digraph of G with respect to an elementary abelian subgroup of order 4 and a non-self-paired suborbit of length 2. A direct inspection of the appropriate subgroups of PGL(2,17) and their coset digraphs reveals that there are six pairwise non-isomorphic digraphs arising in this way. They are listed in Table 1 as digraphs Xio, Xn,..., Xi5. This concludes the proof of Theorem 1.1. 3.3 Proof of Theorem 1.2 We shall say that a positive integer n satisfies condition (i), (ii) or (iii), respectively, if the following holds: (i) n is odd and cube-free; (ii) n = 2am, where a e {1,2, 3} and m is an odd, square-free integer; (iii) n = 2aqbp2, where a € {1,2,3}, b e {0,1} and p, q are distinct odd primes. As in the statement of Theorem 1.2, we assume that r is a connected 2-valent (G, 2)-arc-transitive digraph with G solvable, and that one of the conditions (i), (ii) or (iii) holds for n = | V(r) |. We need to show that either: (a) r is a Pi -digraph; or that (b) n satisfies the condition (iii) and G contains a normal Sylow p-subgroup P, which is elementary abelian of order p2 and such that r/p is a Pi -digraph. Suppose that the theorem is false and let r be a minimal counter-example (in terms of n). In particular, r is not a Pi -digraph. By Lemma 2.1, r is then simple. Since G acts transitively on the vertex-set of r and since the vertex-stabiliser Gv is of order 2s for some s > 2 (see Lemma 3.1), it follows that |G| = |Gv |n = 2sn. 142 Ars Math. Contemp. 11 (2016) 147-156 We shall now prove a few facts about r and G, finally resulting in a contradiction. Fact 0: If N is a semiregular normal subgroup of G, then r/N is a -X -digraph, or n/|N | (and thus also n) satisfies the condition (iii) and the Sylow p-subgroup of g/n is elementary abelian of order p2 and normal in g/n. Proof: Since N is semiregular, by Lemma 2.6, r X r/N is a covering projection, and by Lemma 2.5, r/N is a connected 2-valent (g/n, 2)-arc-transitive digraph. Moreover, since every divisor of an integer satisfying one of the conditions (i), (ii), or (iii) also satisfies one of these conditions, the minimality of the counterexample r implies that either r/N is a -X -digraph or that n/|N| satisfies the condition (iii) and the Sylow p-subgroup of g/n is indeed as claimed. Fact 1: n does not satisfy the condition (i); in particular, n is even. Proof: Assume the contrary (that is, n is odd and cube-free). Since n is odd, the vertex-stabiliser in G is a Sylow 2-subgroup of G, and every 2-subgroup of G is contained in some vertex-stabiliser in G. Let N be a minimal normal subgroup of G. Since G is solvable, N is elementary abelian. If N is a 2-group, then N < Gv for some vertex v, and thus the action of G on the vertices of r is not faithful, implying that r is not simple, a contradiction. Hence N is an elementary abelian group of odd order, and thus acts semiregularly on the vertices of r. By Fact 0, r/N is a -X -digraph, and since its order is odd, it must be isomorphic to n', 0) where n' = n/|N|. Further, by Lemma 2.9 (note that rad(r/N) = 1 = rad(r)), we see that N is not of prime order. Since the order of r is cube-free, it follows that N is elementary abelian of order p2 for some odd prime p. Let us now consider the group g/n acting on r/N. Since r/N = n', 0), by Lemma 2.2, the stabiliser (g/n)vn of a vertex vN of r/N is elementary abelian and normal in g/n. Note also that (g/n)vn = Gvn/n, implying that GvN is normal in G. Let C be the centraliser of N in GvN. If we apply Lemma 3.3 with X = N, Y = Gv N and Z = G, we see that C = N x T for some normal subgroup T of G, isomorphic to a subgroup of Y/N = Gv. In particular, T is a 2-group. Since the order of r is odd and T is a 2-group, T fixes a vertex of r, and being normal in G, it acts trivially on the vertex-set of r. Since r is a simple digraph, it follows that T =1, and thus C = N. Since GvN is normal in G and contains Gv, it contains Gu for every vertex u G V(r). In particular, Gv N contains every involution of G. Together with the fact that N is self-centralising in Gv N this implies that no involution of G centralises N. Now consider the centraliser D of N in G. We have just shown that D has odd order, implying that D is semiregular, and thus, r/D = n'', 0) for some odd integer n''. Moreover, since g/d acts 2-arc-transitively on r/D, the Sylow 2-subgroup S of g/d is the vertex-stabiliser of every vertex of r/D, and is thus normal in r/D, elementary abelian, and of order at least 4. On the other hand g/d embeds into Aut(N) = GL(2,p). By Lemma 3.2, it follows that S is of order 4 and contains an involution that is central in g/d. However, by Lemma 2.2, this implies that n'' is even. This contradiction concludes the proof of Fact 1. Fact 2: The group G does not contain a normal elementary abelian subgroup of order p2 for any odd prime p. Proof: Assume the contrary and note that in view of Fact 1, n then satisfies the condition (iii); that is, n = 2aqbp2 for some a < 3 and b < 1. Moreover, G contains a normal K. Berčič and P. Potočnik: Two-arc-transitive two-valent digraphs of certain orders 143 elementary abelian subgroup P of order p2. Since p is odd, P is semiregular, and by Fact 0, either r/p is a -digraph, or n/|P| = 2aqb satisfies the condition (iii). The latter is clearly false, while the former implies that the conclusion (b) of Theorem 1.2 holds for r, a contradiction. Fact 3: rad(r) > 3; that is, the alternating cycles of r are of length at least 6. Proof: Assume the contrary; that is, rad(r) < 3. Since r is simple, we have rad(r) = 1. Hence rad(r) = 2, and by Lemma 2.11, it follows that r = Pl(A) for some connected 2-valent (G, 3)-arc-transitive digraph A of order 2n. If A is a -digraph, then by formula (2.2), so is r, a contradiction. By the minimality of the counterexample r, this implies that conclusion (b) holds for the pair (A, G) in place of (r, G), and in particular, that G contains a normal elementary abelian subgroup of order p2 for some odd prime p. However, the latter contradicts Fact 2. Fact 4: The group G contains no normal subgroup of odd prime order. Proof: Suppose the contrary and let N be a normal subgroup of G of odd prime order q. Since Gv is a 2-group, N is semiregular. By Fact 3 and Lemma 2.9, r/N is not a -1- digraph. But then Fact 0 implies that n = 2aqp2 and the Sylow p-subgroup P of g/n is normal in g/n and isomorphic to Zp. Let Q be the preimage of P with respect to the quotient projection G 1 g/n. Then Q is a normal subgroup of G of order qp2, containing the normal subgroup N of order q. Let C be the centraliser of N in Q. Since N is abelian and since N has order coprime to its index in Q, we may apply Lemma 3.3 with Z = G, Y = Q and Z = N, to conclude that C = N x P for some normal subgroup P of G, isomorphic to a normal subgroup of q/n. Since the latter is isomorphic to P, we see that P is either trivial, cyclic of order p, or isomorphic to Zp. If P is trivial, then C = N, and q/n embeds into Aut(N), implying that q/n is cyclic. However, q/n is isomorphic to P, which is isomorphic to Zp, a contradiction. Further, by Fact 2, the order of P is not p2. This leaves us with the possibility that |P | = p. Now consider the quotient r/p. Since the order of r/p is 2aqp, Fact 0 implies that r/p is a RX-digraph. But then, by Lemma 2.9, rad(r) = rad(r/p), which is at most 2, since r/p is a RX-digraph, contradicting Fact 3. Fact 5: If N is a minimal normal subgroup of G, then N is semiregular and of order 2 or 4. If |N| = 2, then r/w = pX(m, 2), and if |N| = 4, then r/w = 1-X(m, 1) for some odd integer m. Moreover, exp(r) = 2. Proof: Let m be the odd part of n. By Fact 1, n = 2am where a > 1 and m is cube-free. Let N be a minimal normal subgroup of G. Since G is solvable, N is elementary abelian, and since |G| = 2a+sm, Facts 2 and 4 imply that N is a 2-group. If N is not semiregular, then by Lemma 2.12, r is a -digraph, contradicting our assumptions. Hence N is semiregular, and thus |N | divides n, and therefore |N | = 2l for some integer t satisfying 1 < t < a. By Fact 0, either r/N is a -1 -digraph, or n/|N | satisfies the condition (iii) and the group g/n contains a normal elementary abelian subgroup P of order p2. Suppose first that the latter case occurs. Then n/|N| = 2a-tqbp2 where a - t > 1. Since a < 3, this implies that t € {1, 2}. As in the proof of Fact 4, let Q be the preimage 144 Ars Math. Contemp. 11 (2016) 147-156 of P with respect to the quotient projection G i g/n. Then Q is a normal subgroup of G of order 2tp2, containing the normal subgroup N of order 24. Now consider the centraliser C of N in Q, apply Lemma 3.3 with Z = G, Y = Q and X = N, and conclude that C = N x P for some (possibly trivial) p-group P which is normal in G. If P is trivial, then q/n = P = Z2 embeds into Aut(N) = GL(t, 2). Since t < 2, this is clearly not the case. Hence P is non-trivial, contradicting either Fact 2 or Fact 4. This contradiction shows that the former case occurs, that is r/N = P)X(2a-i-rm, r) for some integer r such that 0 < r < a — t. Let A = r/N and let p : r i A be the corresponding quotient projection. Since a < 3 and t > 1, we see that r < 2. If r = 0, then Lemma 2.13 implies that r is a Pi -digraph, a contradiction. If r = 1, either a = 2 and t = 1, or a = 3 and t G {1,2}. Let v G V(r) and let v' = p(v). Observe that exp(A) = 1 (see Lemma 2.14) and (v')| = 2 for every i > 1. By Lemma 2.8, it follows that |A[(v)| divides 2È|Af (v')| = 2i+1 < 8 for every i > 1. Since |A[(v)| = rad(r) > 3, it follows that |A[ (v)| G {4,8}. If |A[(v)| = |A£(v)|, then exp(r) = 1, and by Lemma 2.4, r is a Pi -digraph, a contradiction. Hence |A[(v)| < |Ar(v)|, implying that |A[(v)| =4 and |A[(v)| = 8 for every i > 2 (hence exp(r) = 2). Moreover, since 8 = |Ar (v) | divides 2t+1, we see that t = 2 and a = 3, implying that A = pi( m, 1), as claimed. Similarly, if r = 2, then a = 3, t = 1 and A = K^m, 2). Hence exp(A) = 2, |A^(v')| = 2 and |Af(v')| = 4 for every i > 2. Moreover, as above, |A[(v)| > 3 and Uï(v)| < |Ar (v)|. In view of Lemma 2.8, it thus follows that |A[(v)| = 2!|A^(v')| = 4, and (v)| = |A^(v)| = 8. In particular, exp(r) = 2, as claimed. This concludes the proof of Fact 5. Fact 6: The order n of r is at most 744. Proof: Let N be a minimal normal subgroup of r and recall Fact 5. Since exp(r) = 2, [30, Theorem 7.1] implies that |Gv | < 24. By Lemma 2.5, also the stabiliser (g/n)vn has order at most 24. By Lemma 3.4, this implies that g/n contains a normal cyclic group y whose order is I for some odd integer I satisfying I > m/(2a+4 - 1), (*) where a is either 1 or 2, depending on whether |N | =4 or |N | =2, respectively. Let Y < G be the preimage of YP with respect to the quotient projection G i g/n, let C be the centraliser of N in Y, and apply Lemma 3.3 to deduce that C = N x T for some cyclic group T G of order dividing £ Since T is cyclic, every subgroup of T is characteristic in T and thus normal in G. If T is non-trivial, this implies that G contains a normal subgroup of odd prime order, contradicting Fact 4. Hence T =1, and C = N. If |N| = 2, then a = 2, N is central in Y, and Y = C = N. However, £ = |Y|/|N|, and thus £ = 1. In view of (*), we see that m < 22+4 — 1 < 63, and therefore n = |N|| V(r/N)| = 2| V(-X(m, 2))| = 8m < 504. If |N | =4, then a = 1, and by (*), we see that m < 31£, and thus n = 4|V(—X(m, 1))| = 8m < 248£. On the other hand, since C = N, the cyclic group Y/N of order £ embeds into Aut(N) = GL(2, 2) = Sym(3), and thus £ < 3. But then n < 3 • 248 = 744. This concludes the proof of Fact 6. Since a census of all simple arc-transitive digraphs of valence 2 is available in [28], we can easily see that no counter-example to the theorem of order at most 1000 exists. This, K. Berčič and P. Potočnik: Two-arc-transitive two-valent digraphs of certain orders 145 however, contradicts Fact 6, and thus proves the theorem. References [1] K. Bercic and P. Potocnik, The magma code for the twenty exceptional digraphs, http:// www.fmf.uni-lj.si/~potocnik/Katja/ATD.htm, accessed 10th October 2014. [2] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I: The user language, J. Symbolic Comput. 24 (1997), 235-265. [3] C.-Y. Chao, On the classification of symmetric graphs with a prime number of vertices, Trans. Amer. Math. Soc. 158 (1971), 247-256. [4] Y. Cheng and J. Oxley, On weakly symmetric graphs of order twice a prime, J. Combin. Theory Ser.B 42 (1987), 196-211. [5] M. Conder, C.-H. Li and P. Potocnik, On the orders of arc-transitive graphs, J. Algebra 421 (2015), 167-186. [6] M. Conder, P. Potocnik and P. Sparl, Some recent discoveries about half-arc-transitive graphs, ArsMath. Contemp. 8 (2015), 149-162. [7] J. D. Dixon and B. Mortimer, Permutation Groups, Graduate Texts in Mathematics 163, Springer-Verlag, New York (1996). [8] Y.Q. Feng, K. Kutnar, D. Marusic and C. Zhang, Tetravalent one-regular graphs of order 4p2, Filomat 28 (2014), 285-303. [9] A. Gardiner and C. E. Praeger, A Characterization of Certain Families of 4-Valent Symmetric Graphs, European J. Combin. 15 (1994), 383-397. [10] M. Ghasemi and P. Spiga, 4-Valent one-regular graphs of order 6p2, Ars Math. Contemp. 9 (2015), 1-18. [11] S. Guest, J. Morris, C. E. Praeger and P. Spiga, On the maximum orders of elements of finite almost simple groups and primitive permutation groups, Trans. Amer. Math. Soc. 367 (2015), 7665-7694. [12] M. Herzog, On finite simple groups of order divisible by three primes only, J. Algebra 10 (1968), 383-388. [13] B. Huppert and W. Lempken, Simple groups of order divisible by at most four primes, Proc. of the F. Scorina Gomel State Univ. 16 (2000), 64-75. [14] A. Malnic, D. Marusic and P. Potocnik, Elementary abelian covers of graphs, J. Algebraic Comb. 20 (2004), 71-97. [15] A. Malnic, D. Marusic, S. Miklavic and P. Potocnik, Semisymmetric elementary abelian covers of the Mobius-Kantor graph, Discrete Math. 307 (2007), 2156-2175. [16] A. Malnic, P. Potocnik, N. Seifter and P. Sparl, Reachability relations, transitive digraphs and groups, to appear in Ars Math. Contemp. 8 (2015), 83-94. [17] A. Malnic, T. Pisanski and A. Zitnik, The clone cover, to appear in Ars Math. Contemp. 8 (2015), 95-113. [18] D. Marusic, Recent developments in half-transitive graphs, Discrete Math. 182 (1998), 219231. [19] D. Marussics, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser.B 73 (1998), 41-76. [20] D. Marusic and R. Nedela, Finite graphs of valency 4 and girth 4 admitting half-transitive group actions J. Aust. Math. Soc. 73 (2002), 155-170. 146 Ars Math. Contemp. 11 (2016) 147-156 [21] D. Marusic, R. Nedela, Partial line graph operator and half-arc-transitive group actions, Math. Slovaca 51 (2001), 241-257. [22] D. Marusic, R. Nedela, On the point stabilizers of transitive groups with non-self-paired suborbits of length 2, J. Group Theory 4 (2001), 19-43. [23] D. Marusic and P. Potocnik, Classifying 2-arc-transitive graphs of order a product of two primes, Discrete Math. 244 (2002), 331-338. [24] D. Marusic and P. Potocnik, Bridging semisymmetric and half-arc-transitive actions on graphs, European J. Combin. 23 (2002), 719-732. [25] D. Marusic and C. E. Praeger, Tetravalent graphs admitting half-transitive group actions: alternating cycles, J. Combin. Theory Ser. B 75 (1999), 188-205. [26] D. Marusic and R. Scapellato, Classifying vertex-transitive graphs whose order is a product of two primes, Combinatorica 14 (1994), 187-201. [27] P. M. Neumann, Finite Permutation Groups, edge-coloured graphs and matrices, in Topics in groups theory and computations (ed. M. P. J. Curran), Academic Press, London (1977). [28] P. Potocnik, P. Spiga and G. Verret, A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two, Ars Math. Contemp. 8 (2015), 133-148. [29] P. Potocnik, P. Spiga and G. Verret, A census of 2-valent arc-transitive digraphs, http:// www.fmf.uni-lj.si/~potocnik/work.htm [30] P. Potocnik and G. Verret, On the vertex-stabiliser in arc-transitive digraphs, J. Combin. Theory Ser. B. 100 (2010), 497-509. [31] R. PoZar, Sectional split extensions arising from lifts of groups, Ars. Math. Contemp. 6 (2013), 393-408. [32] R. PoZar, Some computational aspects of solvable regular covers of graphs, J. Symbolic Comp., 70 (2015), 1-13. [33] C. E. Praeger, Imprimitive symmetric graphs, Ars Combin. 19 (1985), 149-163. [34] C. E. Praeger, An O'Nan-Scott Theorem for finite quasiprimitive permutation groups, and an application to 2-arc transitive graphs, J. London Math. Soc.(2) 47 (1993), 227-239. [35] C. E. Praeger, Highly arc transitive digraphs, European J. Combin. 10 (1989), 281-292. [36] C. E. Praeger, R. J. Wang and M. Y. Xu, Symmetric graphs of order a product of two distinct primes J. Combin. Theory Ser B 58 (1993), 299-318. [37] C. E. Praeger and M. Y. Xu, A characterization of a class of symmetric graphs of twice prime valency, European J. Combin. 10 (1989), 91-102. [38] A. Seress, On vertex-transitive, non-Cayley graphs of order pqr, Discrete Math. 182 (1998), 279-292. [39] P. Sparl, A classification of tightly attached half-arc-transitive graphs of valency 4, J. Combin. Theory Ser. B 98 (2008), 1076-1108. [40] P. Sparl, On the classification of quartic half-arc-transitive metacirculants, Discrete Math. 309 (2009), 2271-2283.