ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 12 (2017) 361-381 A normal quotient analysis for some families of oriented four-valent graphs Jehan A. Al-bar *, Ahmad N. Al-kenani, Najat Mohammad Muthana King Abdulaziz University, Jeddah, Saudi Arabia Cheryl E. Praeger t The University of Western Australia, Crawley, Australia; also affiliated with King Abdulaziz University, Jeddah, Saudi Arabia Received 28 June 2016, accepted 20 December 2016, published online 12 February 2017 We analyse the normal quotient structure of several infinite families of finite connected edge-transitive, four-valent oriented graphs. These families were singled out by Marusic and others to illustrate various different internal structures for these graphs in terms of their alternating cycles (cycles in which consecutive edges have opposite orientations). Studying the normal quotients gives fresh insights into these oriented graphs: in particular we discovered some unexpected 'cross-overs' between these graph families when we formed normal quotients. We determine which of these oriented graphs are 'basic', in the sense that their only proper normal quotients are degenerate. Moreover, we show that the three types of edge-orientations studied are the only orientations, of the underlying undirected graphs in these families, which are invariant under a group action which is both vertex-transitive and edge-transitive. Keywords: Edge-transitive graph, oriented graph, cyclic quotient graph, transitive group. Math. Subj. Class.: 05C25, 20B25, 05C20 *This project was funded by the Deanship of Scientific Research (DSR), King Abdulaziz University, Jeddah, under grant no. HiCi/H1433/363-1. The authors, therefore, acknowledge with thanks DSR technical and financial support. 1 corresponding author E-mail address: jalbar@kau.edu.sam (Jehan A. Al-bar), analkenani@kau.edu.sa (Ahmad N. Al-kenani), nmuthana@kau.edu.sa (Najat Mohammad Muthana), cheryl.praeger@uwa.edu.au (Cheryl E. Praeger) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 362 Ars Math. Contemp. 12 (2017) 383-413 1 Introduction The graphs we study are simple, connected, undirected graphs of valency four, admitting an orientation of their edges preserved by a vertex-transitive and edge-transitive subgroup of the automorphism group, that is, graphs of valency four admitting a half-arc-transitive group action. Many of these graphs arise as medial graphs for regular maps on Riemann surfaces [8, 9]. The work of Marusic, summarised in [8], demonstrated the importance of a certain family of cyclic subgraphs for understanding the internal structure of these graphs, namely their alternating cycles. These are cycles in which each two consecutive edges have opposite orientations. They were introduced in [7] and their basic properties were studied in [7, 10]. The families of oriented graphs studied in this paper were singled out in [9, 10] because they demonstrate three different extremes for the structure of their alternating cycles: namely the alternating cycles are 'loosely attached', 'antipodally attached' or 'tightly attached' (see Subsection 1.2). These families are based on one of two infinite families of underlying unoriented valency four graphs (called X(r) and Y(r) for positive integers r), and for each family three different edge-orientations are induced by three different subgroups of their automorphism groups (Section 1.3); the three different edge-orientations correspond to the three different attachment properties of their alternating cycles. In this paper it is shown in Theorem 1.1 that these are essentially the only edge-orientations of the underlying graphs which are invariant under a half-arc-transitive group action. Our approach is to study the normal quotients of these 'X-graphs' and 'Y-graphs' (as explained below), and in doing so we discover that graphs from a third family arise, the 'Z-graphs'. We find (Theorem 1.3) that normal quotients of the X-graphs are sometimes X-graphs, sometimes Y-graphs, and sometimes Z-graphs, and the same is true for normal quotients of the Y-graphs. In addition we determine in Theorem 1.2 those oriented graphs in these families which are 'basic' in the sense that all their proper normal quotients are degenerate (see Subsection 1.1). 1.1 Graph-group pairs and their normal quotients The normal quotient approach was introduced in [2] to study oriented graphs, focusing on the structure of certain quotient graphs rather than subgraphs. For a connected oriented four-valent graph r with corresponding vertex- and edge-transitive group G preserving the edge-orientation, a normal quotient of (r, G) is determined by a normal subgroup N of G. It is the graph rN with vertices the N-orbits on the vertices of r, and with distinct N-orbits B, C adjacent provided there is some edge of r between a vertex of B and a vertex of C. The normal quotient theory in [2] asserts (with specified degenerate exceptions) that the normal quotient rN has valency four, and inherits an edge-orientation from r which is preserved by the quotient group G/N acting transitively on vertices and edges, and, moreover, r is a cover of rN (that is, for adjacent N-orbits B, C, each vertex of B is adjacent to exactly one vertex of C). We call a pair (r, G) basic if the only proper normal quotients (that is, taking N =1) are degenerate. Each pair (r, G) has at least one basic normal quotient, (more details are given in Section 2, and see [1, 2]). For the pairs (r, G) we study in this paper, there is always a basic normal quotient which lies in one of the families (possibly a different family from the family containing (r, G)). Thus, although all the graph-group pairs in a given family share the same properties of their alternating cycles (Remark 1.4), the structure of J. A. Al-bar et al.: A normal quotient analysis for some families of oriented four-valent graphs 363 the family can be further elucidated by studying the much smaller subfamily of basic pairs. 1.2 The alternating cycles of Marusic Let OG(4) denote the set of all graph-group pairs (r, G), where r is a connected graph of valency four, G is a vertex-transitive and edge-transitive subgroup of automorphisms, and G preserves an orientation of the edges. In particular G is not transitive on the arcs of r (ordered pairs of vertices which form an edge), and such a group action is called half-arc-transitive. Alternatively we could interpret each pair (r, G) G OG(4) as consisting of a connected, undirected graph r of valency four, and a group G of automorphisms acting half-arc-transitively. Such a group action determines an edge-orientation of r (up to reversing the orientation on every edge). It is possible for a single graph to have different edge-orientations determined by different subgroups of automorphisms. This is the case with the examples in Subsection 1.3 (a) and (b). By viewing the fundamental objects of study as undirected graphs endowed with (perhaps several) edge-orientations, we are able to give a unified discussion of all possible edge-orientations preserved by half-arc-transitive group actions. Our notation is therefore slightly different from the papers [9, 10] where different names for the same graph are used for different edge-orientations. The alternating cycles of (r, G) (defined above), are determined by the edge-orientation. They partition the edge set, they all have the same even length, denoted by 2 • r (r, G), where r(r, G) is called the radius of (r, G), and if two alternating cycles share at least one vertex, then they intersect in a constant number a(r, G) of vertices, called the attachment number, such that a(r, G) divides 2 • r(r, G) [7, Proposition 2.4]. The radius can be any integer greater than 1 ([7, Section 3] and [10, Section 4]), and the attachment number can be any positive integer [12, Theorem 1.5]. It is possible that a(r, G) = 2 • r(r, G) and all such pairs (r, G) were characterised by Marusic in [7, Proposition 2.4(ii)]. Otherwise, if a(r, G) < 2 • r(r, G), then r is a cover of a (possibly smaller) quotient graph r' admitting a (possibly unfaithful) action G' of G such that (r', G') G OG(4) and the attachment number a(r', G') is either 1, 2 or r(r', G'), [10, Theorem 1.1 and Theorem 3.6]. For this reason attention has focused on families of examples (r, G) g OG(4) for which a(r, G) is 1,2 or r(r, G), and such pairs are said to be loosely attached, antipodally attached or tightly attached, respectively. As we already mentioned, graphs in the families we examine have one of these properties, and the structure of their alternating cycles was studied by Marusic and others [4, 6, 7, 9, 10, 11, 12, 13]. 1.3 The families of oriented graphs and our results We describe the underlying graphs and their edge-orientations. (a) The first three families of oriented graphs are all based on the same family of graphs, namely the Cartesian product X (r) = C2r □ C2r of two cycles of length 2r, for a positive integer r. The graph X(r) has vertex set Z2r x Z2r, such that (i, j) is adjacent to (i ± 1, j) and (i, j ± 1) for all i, j G Z2r .If r =1 then X (1) = C4, a 4-cycle. If r > 2, then X (r) has valency 4 and its automorphism group is G(r) = Aut X(r) = D4r I Z2 = D|r x Z2, 364 Ars Math. Contemp. 12 (2017) 383-413 with generators Mi : (i j) —> (i + 1,M2 : j) —> j + 1), 0t : j) —> j), ^2 : j) —> (i -j) t : j) —> (j,i). The group G(r) is arc-transitive of order 32r2, and the stabiliser of the vertex x = (0,0) is G(r)x = (ai, 3) at least one quotient action d2m or Zm (a.4) Let s be an odd integer, s > 3, and let Z(s) = Cs □ Cs (that is, the graph X(r) with 2r replaced by s); let , , t have the same meanings as above (as permutations of the set Zs x Zs); define the edge-orientation as in (a.3); and call the corresponding group G3z(s) = (mi,M2,t). (b) The last three families of oriented graphs are all based on certain quotients of the graphs in part (a). Define the (undirected) graph Y(r) as the quotient of X(r) modulo the orbits of the normal subgroup M(r) := ((^i^2)r) of G(r). Thus the vertices of Y(r) are the 2-element subsets {(i, j), (i + r, j + r)}, for i, j e Z2r, and the vertex {(i, j), (i + r, j + r)} of Y(r) is adjacent to {(i ± 1, j), (i + r ± 1, j + r)} and {(i, j ± 1), (i + r, j + r ± 1)}. The graph Y(1) = K2 and, for r > 2, Y(r) has valency 4, and admits an arc-transitive action of the quotient H(r) := G(r)/M(r). Moreover, X(r) is a cover of Y(r). In particular, Y(2) = K4,4, a complete bipartite graph. For k = 2,3 with r > 2, and also for k = 1 with r even, we have M(r) < Gk (r) and we define Hk(r) := Gk(r)/M(r). Then the graph-group pair (Y(r),Hk(r)) e OG(4) (Lemma 3.3). It is the normal quotient of the pair (X(r), Gk(r)) relative to M(r), and by [2, Theorem 1.1], Y(r) inherits the kth-edge-orientation from X(r). For any of the graphs X(r), Y(r), Z(s), each of the edge-orientations defined above is invariant under some edge-transitive subgroup of automorphisms (by Theorem 1.2), and these are essentially the only such edge-orientations for these graphs. Theorem 1.1. Let r = X(r) with r > 2, or r = Y(r) with r £ {1, 2,4}, or r = Z(s) with s odd, s > 1. Then, up to conjugation in Aut r, and up to reversing the orientation on each edge, the only edge-orientations of r invariant under a half-arc-transitive subgroup of Aut r are those defined in Subsection 1.3. We prove Theorem 1.1 in Section 4. By [2, Lemma 3.3], each graph-group pair (r, G) e OG(4) is a normal cover of at least one basic pair in OG(4). It turns out that the graph-group pairs (X(r), Gk(r)), (Y(r), Hk(r)), and (Z(s), G3Z(s)) all lie in OG(4), and are all normal covers of at least one basic pair from one of these families, but not necessarily from the same family (Remark 3.1 (c)). Our main results identify which of these pairs is basic (Theorem 1.2), and present some of their interesting normal quotients (Theorem 1.3). The types of basic graph-group pairs are defined according to the kinds of degenerate normal quotients they have. These are summarised in Table 1, taken from [2, Table 2]. Theorem 1.2. Let (r, G) be one of the graph-group pairs in Table 2. Then (r, G) e OG(4). Moreover (r, G) is basic if and only if the conditions in the 'Conditions to be Basic' column hold, and in this case, the basic type is given in the 'Basic Type' column. 366 Ars Math. Contemp. 12 (2017) 383-413 Table 2: Conditions for (T, G) to be basic in Theorem 1.2. (Refer to Lemma 6.2.) (r, G) Conditions Conditions to be Basic Basic Type (X (r),Gfc (r)) (Y(r), Hk(r)) (Y (r),Hfc (r)) (Z (s),Gs z (s)) all k and r all k and r even k > 1 and r odd s > 3 odd k =1, r odd prime all k and r = 2 k = 2, r odd prime s odd prime cycle cycle biquasiprimitive cycle We verify membership of OG(4) in Lemma 3.3, and prove the assertions in Table 2 in Lemma 6.2. The normal quotients we explore are those modulo the following subgroups of G(r) and/or G3Z(s). We note that |Mi| is 2r or s, when interpreting m as an element of G(r) or G3Z(s), respectively. For each divisor a of 2r or of s, as appropriate, define N(a) = (Mf,Mf> if a |M (1.1) M(a) = ((mim2)a,M?°> if 2a | M N(2, +) = (m?,m2,^2> < G2(r). If = 2r, then each of N(a), M(a) is normal in the full automorphism group G(r) of X(r), and if a | r, then N(2a) is a subgroup of M(a) of index 2; if |^1| = s is odd, then N(a) < G3Z(s) (and M(a) is not defined). We also consider: J = (MiM2> = Zt, and K = >= D2t (1.2) where t = 1 G {2r, s}, and if 1 = 2r, also J (+) = (M1M2, Mi) and K (+) = (mm-1,T, Mi>. (1.3) If t = 2r then the four subgroups in (1.2) and (1.3) all contain M(r) and are normal in G3(r), while if t = s then J, K are normal in G3Z(s). For an arbitrary subgroup L of G(r), we write L := LM(r)/M(r), so, for example, H(r) = G(r) and Hk(r) = Gk(r), and we also consider the subgroups M(a) and N(a). Note that M(r) < N(a) if and only if ^ is odd if and only if N(a) = M(f). (1.4) Theorem 1.3. Let (r, G) be a graph-group pair (X(r), Gk(r)), (Y(r), Hk(r)), or (Z(s), G3Z (s)), where k G {1, 2, 3}, s > 3 is odd, r > 2, and in the case of (Y(r), H1(r)), r is even. (a) Then (r, G) has proper non-degenerate normal quotients (rN, G/N),for (r, G), N and the 'Conditions' as in one of the lines of Table 3. (b) also (r, G) has degenerate normal quotients (rN, G/N), for N, G as in one of the lines of Table 4. We prove parts (a) and (b) of Theorem 1.3 in Lemmas 5.1 and 5.2, respectively. We do not claim that Theorem 1.3 classifies all the normal quotients for these graph-group pairs. J. A. Al-bar et al.: A normal quotient analysis for some families of oriented four-valent graphs 367 Table 3: Non-degenerate normal quotients of (T, G) for Theorem 1.3, with N as in (1.1) and a > 1. (Refer to Lemma 5.1.) (r,G) N (rN, G/N ) Conditions on k, a, r (X (r),Gk(r)) N (2a) (X(a), Gk (a)) a < r (X (r),Gk(r)) M (a) (Y(a), Hk (a)) — even, and a even if k = 1 a ' (X (r),Gs (r)) N(a) (Z (a),G3z (a)) a odd (Y(r), Hk(r)) N (2a) (X (a), Gk (a)) r even a (Y (r),Hk (r)) M (a) (Y(a), Hk (a)) > 2 even, and a even if k =1 (Y (r),Hs(r)) N (a) (Z (a),G3z (a)) a odd (Z (s),G3z (s)) N(a) (Z (a),G3z (a)) a < s Table 4: Degenerate normal quotients of (T, G) for Theorem 1.3, with N as in (1.1), (1.2) or (1.3). (Refer to Lemma 5.2.) N in Gk(r) N in Hk(r) N in Gsz(s) (rw, G/N) Conditions N(2) N (2) - (C4,Ds) k = 1, 3, with r even for Hk (r) N (2, +) N (2, +) - (C4, Z4) k = 2 with r even for Hk (r) - N (2, +) - (K2,Z2) k = 2, r odd - N (2) - (K2,Z2) k = 3, r odd J J J (Ct, D2t) k = 3, t e {2r, s} K K K (Ct,Zt) k = 3, t e {2r, s} J (+) J (+) - (Cr, D2r ) k=3 K (+) K (+) - (Cr, Zr ) k=3 368 Ars Math. Contemp. 12 (2017) 383-413 Remark 1.4. (a) When defining (Z(s), G3Z(s)) with s odd, we only consider the third edge-orientation since, for s odd, elements of Zs do not have a well-defined parity, and so the definitions of the first and second edge-orientations do not make sense for the graph Z (s). Also, when defining (Y(r), Hk(r)), we require that r should be even when k = 1, since when k = 1 and r is odd, there are oriented edges in both directions between adjacent Y(r)-vertices, so the first edge-orientation of X(r) is not inherited by Y(r). (b) The nomenclature in (a.4) may seem clumsy. However we decided to keep the same names for the graphs X (r), Y(r) in order to facilitate reference to [9, 10] for their other properties, as follows. (i) It is pointed out in [10, Section 2] and [9, Page 161], that for r > 3, the oriented graph-group pairs (X (r), Gk (r)) are loosely attached with radius 2, antipodally attached with radius r, and tightly attached with radius 2r, for k = 1, 2,3, respectively. Note that the graph X(r) with the kth edge-orientation is called Xk (r) in [10]. (ii) It is remarked in [10, Section 2], that if r > 3, then the oriented graph-group pairs (Y(r), Hk (r)) (with r even if k = 1) are loosely attached with radius 2, antipodally attached with radius r, and tightly attached with radius r, for k = 1, 2, 3, respectively. (iii) The pairs (X(r),G2(r)) and (Y(r),H2(r)) were also studied by Marusic and Nedela, where they were characterised in [9, Props. 3.3, 3.4] as the only pairs with stabilisers of order at least 4, and such that every edge lies in precisely two oriented 4-cycles. (c) By Theorems 1.2 and 1.3, the graph-group pairs all have basic normal quotients, sometimes more than one. We summarise our findings. (i) (X(r), Gi(r)), and also (Y(r), Hi(r))(r even), have basic normal quotients (Y(2), H1(2)) if r is even and (X(a), G1(a)) for odd primes a | r; (ii) (X(r), G2(r)), and also (Y(r), H2(r)), have as basic normal quotients (Y(a), H2(a)) for primes a | 2r; (iii) (X(r), G3(r)), and also (Y(r), H3(r)), have as basic normal quotients (Y(2), H3(2)) if r is even and (Z(a), G3Z(a)) for odd primes a | r; (iv) (Z(s), G3Z(s)) (s odd) has basic normal quotients (Z(a), G3Z(a)) for odd primes a | s. 2 Preliminaries: normal quotients of pairs in OG (4) For fundamental graph theoretic concepts please refer to the book [5], and for fundamental notions about group actions please refer to the book [3]. For permutations g of a set X, we denote the image of x g X under g by xg. A permutation group on a set X is semiregular if only the identity element fixes a point of X; the group is regular if it is transitive and semiregular. If a permutation group G on X has a normal subgroup K < G such that K is regular, then (see [3, Section 1.7]) G is a semidirect product G = K.Gx, where Gx is the stabiliser of a point x g X. Moreover, we may identify X with K in such a way that x = 1K, K acts by right multiplication and Gx acts by conjugation. Many of the groups we study in this paper have this form. J. A. Al-bar et al.: A normal quotient analysis for some families of oriented four-valent graphs 369 As mentioned in Section 1, normal quotients of graph-group pairs (T, G) G OG(4) are usually of the form (rN, G/N), they lie in OG(4), and r is a cover of rN, where N < G. The only exceptions are the degenerate cases when rN consists of a single vertex (if N is transitive), or a single edge (if the N-orbits form the bipartition of a bipartite graph r), or when rN is a cycle possibly, but not necessarily, inheriting a G-orientation of its edges, [2, Theorem 1.1]. Thus (r, G) G OG(4) is basic if all of its proper normal quotients (that is, the ones with N = 1) are degenerate. For a graph-group pair (r, G) G OG(4) and vertex x, the out-neighbours of x are the two vertices y such that x ^ y is a G-oriented edge of r. An isomorphism between graph-group pairs (r, G), (r', G') is a pair (f, y) such that f : r ^ r' is a graph isomorphism, y : G ^ G' is a group isomorphism, and (xg)f = (xf for all vertices x of r and all g G G. Lemma 2.1. Suppose that (r, G) G OG(4), N < G, and (f, y) is an isomorphism from (rN, G/N) to (r', G'). Let M be the set of all normal subgroups M of G such that N < M and M is the kernel of the G-action on the M-vertex-orbits in r. Then, for each M G M, (f, y) induces an isomorphism from (rM, G/M) to (rM, G'/M), where M = (M/N)y, and each normal quotient of (r', G') corresponds to exactly one such normal quotient (rM, G/M). Proof. The isomorphism y : G/N ^ G' determines a one-to-one correspondence M ^ (M/N)y between the set of all normal subgroups of G which contain N, and the set of all normal subgroups of G', and moreover, setting M = (M/N)y, y induces an isomorphism yM : G/M ^ G'/M given by Mg ^ M(Ng)y. For normal quotient graphs rM, the induced group action is G/M, where M is the kernel of the G-action on the M-orbits. Thus rM = Tm, and the normal quotients of (r, G) relative to normal subgroups M containing N are precisely the normal quotients (rM, G/M), for M G M. For each M G M, the graph isomorphism f : rN ^ r' induces a graph isomorphism fM : rM ^ rM, where fM maps the M-vertex-orbit xM in r to the M-vertex-orbit in r' containing (xN)f. By the definition of (f, y) we have ((xN)Ng)f = ((xN)f )(Ng^ for each vertex x of r and each g g G. It follows that ((xM)Mg)fM = ((xMf )(Mg)vM for each vertex x of r and each g g G, and hence (fM, yM) is an isomorphism from (rM, G/M) to (rM, G'/M). This property of (f, y) implies that normal subgroups containing N with the same vertex-orbits in r correspond to normal subgroups of G' with the same vertex-orbits in r', and vice versa. Thus, on the one hand, distinct subgroups in M correspond to distinct normal quotients of (r', G'). Also, on the other hand, each K < G' such that K is the kernel of the G'-action on the K-vertex-orbits in r' is of the form K = (M/N)y, where N < M and M is the kernel of the G-action on the M-vertex orbits in r. □ 3 Each graph-group pair (r, G) in Theorem 1.2 lies in OG (4) First we consider X(r) and Gk (r) for k < 3 and r > 3. Recall the definitions of the edge orientations and the generators Mi, M2, ^2, t, from Subsection 1.3 (a). We make a few comments about the various edge orientations. Remark 3.1. We view the vertex set of X (r) as a 2r x 2r grid with rows and columns labeled 0,1,..., 2r - 1 (in this order, increasing to the right and increasing from top to 370 Ars Math. Contemp. 12 (2017) 383-413 bottom), and with the vertex (i, j) in the row i, column j position. The edges of X(r) then are either horizontal if they join vertices with equal first entries, or vertical if they join vertices with equal second entries. It may be helpful to use this point of view when reading the proofs below. In particular it aids a description of the various edge orientations. (1) In the first edge-orientation, for i even, the horizontal edges in row i are oriented from left to right (except of course that the edge from (i, 2r - 1) is joined to (i, 0)), and for i odd, the horizontal edges in row i are oriented from right to left. Similarly, for j even, the vertical edges in column j are oriented downwards and those in column j, for odd j, are oriented upwards. (2) In the second edge-orientation, both the rows and the columns are alternating cycles, arranged in such a way that, for each i, j, the sequence (i,j), (i,j + 1), (i + 1,j + 1), (i + 1,j) forms a directed 4-cycle, oriented from left to right if i + j is even, and from right to left if i + j is odd. (3) Finally, in the third edge-orientation, all the horizontal edges are oriented from left to right, and all the vertical edges are oriented downwards. Lemma 3.2. Let k < 3 and r > 2. Then the group Gk (r) preserves the kth edge-orientation of X (r). Proof. We consider the cases k = 1,2, 3 separately. In each case, for each generator of Gk(r), we consider its actions on a horizontal edge E in row i joining (i, j) to (i, j + 1), and on a vertical edge D in column j joining (i, j) to (i + 1, j). (1) Firstly maps E to the horizontal edge E' joining (i + 1, -j) to (i + 1, -j -1), since ^1a2 moves row i to row i + 1 (by and then reflects it across a vertical axis through the 0th-column (by ct2). Thus if E is oriented from left to right, then E' is oriented from right to left (and vice versa), and since horizontal edges in row i and row i + 1 have opposite orientations (see Remark 3.1(1)), it follows that ^1a2 preserves the orientation of horizontal edges. Also ^1a2 maps D to the vertical edge joining (i +1, - j) to (i + 2, -j), and since j, - j have the same parity, edges in columns j and - j have the same orientation (see Remark 3.1(1)). Thus ^1a2 preserves the first edge-orientation on all edges. An exactly similar argument (interchanging the roles of rows and columns) shows that ^2a1 also preserves the first edge-orientation. Finally t swaps the horizontal edge E in row i with the vertical edge E' in column i joining (j, i) to (j +1, i). If i is even then E is oriented from left to right and E' is oriented downwards, so the orientation is preserved. Also, if i is odd then E is oriented from right to left and E' is oriented upwards, and again the orientation is preserved. (For example, the oriented edge (1, 2) ^ (1,3) is swapped with the oriented edge (2,1) ^ (3,1).) Similarly the action of t preserves the orientation of D. Thus t preserves the first edge-orientation. (2) Firstly maps E to the horizontal edge E' joining (i + 2, j) to (i + 2, j + 1) and E, E' have the same orientation; and maps D to the vertical edge D' joining (i + 2, j) to (i + 3, j) and D, D' have the same orientation. Thus preserves the second edge-orientation. Similar arguments show that ^2 and also preserve the second edge-orientation. Next, a1 maps E to the horizontal edge E' in row -i joining (-i, j) to (-i, j + 1) and since i+j and -i+j have the same parity, the edges E, E' have the same orientation; J. A. Al-bar et al.: A normal quotient analysis for some families of oriented four-valent graphs 371 similarly < maps D to the vertical edge D', still in column j, joining (—i, j) to (—i -1, j) and we see again that D, D' have the same orientation. Thus < preserves the second edge-orientation. An exactly similar argument shows that also <2 preserves the second edge-orientation. Finally maps E to the vertical edge E' joining (j + 1, i) to (j + 2, i) and since i + j and j + 1 + i have opposite parities, the orientation of E is preserved under the action of ; and maps D to the horizontal edge D' joining (j + 1, i) to (j + 1, i + 1) and for the same reason the orientation of D is preserved under the action of r^1. Thus preserves the second edge-orientation. (3) Firstly, since and map E to a horizontal edge and D to a vertical edge, and since all horizontal edges have the same orientation, and all vertical edges have the same orientation (see Remark 3.1(3)), it follows that and preserve the third edge-orientation. Finally t swaps horizontal and vertical edges, and since all horizontal edges are oriented from left to right, and all vertical edges are oriented downwards, it follows that t also preserves the third edge-orientation. □ Next we prove membership of OG(4). Recall that, for a subgroup L < G(r) we write L = LM(r)/M(r) for the corresponding subgroup of H(r) = G(r)/M(r). Lemma 3.3. Let k < 3, r > 2, and let s > 1 be odd. Let (r, G) be one of (X(r), Gk(r)), (Y(r),Hfc(r)) (with r even if k = 1), or (Z(s),G3Z(s)). Then (r, G) G OG(4). Proof. It is easy to check that the graphs X(r) and Z(s) are connected. Thus, once we have proved that Gk(r) acts half-arc-transitively on X(r), and G3Z(s) acts half-arc-transitively on Z(s), it follows from Lemma 3.2 that (X(r),Gfc(r)) G OG(4) and (Z(s),G3Z(s)) G OG(4). Further, as (Y(r),Hk(r)) is a normal quotient of (X(r),Gk(r)) relative to M(r) = Z2, its membership in OG(4) follows from [2, Theorem 1.1]. It therefore remains to prove that the actions on X(r) and Z(s) are half-arc-transitive. First we consider X(r). The subgroup L := N(2) = (^12) x (^22) < G(r) is contained in Gk(r), for each k, and the L-orbits on vertices are the following four subsets. Aee = {(i, j) | i, j are both even}, Aeo = {(i, j) | i is even, j is odd}, (3.1) A0e = {(i,j) | i is odd, j is even}, A00 = {(i,j) | i,j are both odd}. Writing = Lg for each g G G(r), we note that G(r)/L = (/x1, /x2, 1 since M % H. Then |H| = |H : M n H| • |M n H| = |MH : M| • (4r2/S) divides 8 • (4r2/S), so S | 4 or S = 2 according as |H| = 8r2 or 16r2. Note that it is sufficient to prove that H < G2(r) (up to conjugation in A), since the edge-orientations preserved by H and G2(r) are then the same as both act half-arc-transitively. Let n : M ^ (^i} denote the natural projection map, for i = 1,2. J. A. Al-bar et al.: A normal quotient analysis for some families of oriented four-valent graphs 375 We claim that nj(M n H) = (m®) for at least one i. Suppose that this does not hold. Then, since S < 4, it follows that M n H = (m2,m2), S = 4, so Hx = (aia2) and A = MH. Since A = MH it follows that H contains elements of the form h = tm1m2 and h' = m2 , and we may assume that i, j, i', j' all lie on {0,1} since m1, m2 lie in H. Since neither t nor a1 lies in H, (i, j) = (0,0) = (i', j'). By Lemma 4.2 (a), H does not contain either or a2^2 = ( 2, rN has valency 4, and the mapping f : Ajj —>• (i, j) defines a graph isomorphism from rN to X(a/2) if a is even, or to Z(a) if a is odd. By [2, Theorem 1.1], the group induced by G on the quotient rN is precisely G/N, and (rN, G/N) G OG(4). In particular N is the kernel of the G-action on the set of N-orbits in r. Write g := Ng for elements of the quotient group G/N. If a is even, then it follows from the definitions of the generators m1, /2, °i, t of G(r), given in Subsection 1.3, that the induced maps M1, /r2, ^i, r acting on rN correspond to the respective generators for the smaller group G(a/2) acting on X(a/2). This natural correspondence defines a group isomorphism G(r)/N ^ G(a/2) which restricts to an isomorphism y : G/N ^ Gk (a/2). We conclude that (f, y) defines an isomorphism from (rw, G/N) to (X(a/2), Gfc (a/2)). Thus the first line of Table 3 is valid. Similarly if a is odd, then the maps /i1,/i2, r acting on rN induced from the generators m1,M2,t (for G3(r) or G3Z(s)) correspond to the respective generators for the smaller group G3Z(a) acting on Z(a), and we obtain an isomorphism from (rN, G/N) to (Z(a), G3Z (a)). Thus lines 3 and 7 of Table 3 are also valid. Suppose now that t = 2r above, so r = X(r). If a and 2; are both even then by (1.4), N(a) contains M(r), and it follows by Lemma 2.1 (taking N = M(r) in that result) that the quotient of (Y(r),Hk(r)) modulo N(a) is isomorphic to the quotient of (X(r), Gk(r)) modulo N(a), and we have just shown that this latter quotient is isomorphic to (X(a/2), Gk(a/2)). Thus line 4 of Table 3 is valid. Similarly if a is odd then 2; is even, and again by (1.4), N(a) contains M(r). The same argument now yields that the quotient of (Y(r), Hk(r)) modulo N(a) is isomorphic to (Z(a), G3Z(a)), proving that line 6 of Table 3 is valid. It remains to consider lines 2 and 5 of Table 3. We continue to let (r, G) be the pair (X(r), Gk(r)), and we note that, if a normal quotient of (r, G) modulo M is 4-valent, then by [2, Theorem 1.1], M is the kernel of the G-action on the set of M-vertex-orbits in r. Consider now M = M(a) where a | r (so 2; is even) and 1 < a < r. Since M C G = Gk (r), we must have a even when k =1. Applying Lemma 2.1 with (r', G') = (X(a), Gk (a)) and N = N(2a), we find that the quotient of (r, G) modulo M is isomorphic to the quotient of (X(a), Gk(a)) modulo the image of M under projection from G to G/N = Gk(a), namely ((/r1/r2)a). Thus the latter normal quotient is (Y(a), Hk (a)), proving that line 2 of Table 3 is valid. For the final line, line 5, we apply Lemma 2.1 with (r', G') = (Y(r),Hk(r)) and N = M(r), where r is even when k = 1. Consider M = M(a), where a | r and 1 < a < r, and note that N < M. We wish to take the quotient of (r', G') modulo M = M(a)M(r)/M(r), and we note that 1 < M < Hk (r) if and only if a < r, and also a is even when k =1. Suppose this is the case. Then by Lemma 2.1, the quotient of (r, G) modulo M is isomorphic to the quotient of (Y(r), Hk(r)) modulo the image M of M(a) under projection from G to G/N = Hk(r). We already proved that the former normal J. A. Al-bar et al.: A normal quotient analysis for some families of oriented four-valent graphs 377 quotient (rM, G/M) is isomorphic to (Y(a), (a)). This proves that line 5 of Table 3 is valid. □ Next we consider normal quotients in Table 4. Recall the definitions of the subgroups in (1.1), (1.2) and (1.3). Lemma 5.2. For r, G as in Theorem 1.3 (b), and for N as in one of the lines of Table 4, the assertions about the normal quotient (rN, G/N) are valid. Proof. The N(2)-vertex-orbits on X(r) are the four subsets given in (3.1). It is straightforward to check that the underlying quotient graph of X(r) modulo N(2) is a cycle C4. With the first and third edge-orientations (that is, k = 1 or 3), there are oriented edges in both directions between the adjacent N(2)-orbits, so the cyclic quotient is unoriented, N(2) is the kernel of the action on the N(2)-vertex-orbits, and the induced group is D8. Thus line 1 of Table 4 is valid for N in Gk (r) with k = 1,3. Moreover in these cases, if r is even, then N(2) contains M(r) by (1.4), and it follows from Lemma 2.1 that the quotient of (Y(r), (r)) modulo N(2) is isomorphic to the quotient of (X(r), Gk(r)) modulo N(2), namely (C4, D8), proving the rest of line 1 of Table 4. On the other hand, if k = 2, then the edges of the quotient graph of X(r) modulo N(2) (which is a 4-cycle) are oriented Aee ^ Aeo ^ Aoo ^ Aoe ^ Aee, the kernel of the G2(r)-action on the N(2)-vertex-orbits is N(2, +), and G2(r)/N(2, +) = Z4. Thus line 2 of Table 4 is valid for N in G2(r). If r is even, then M(r) < N(2, +) and arguing as in the previous paragraph, the normal quotient of (Y(r), H2(r)) modulo N(2, +) is also (C4, Z4), proving the rest of line 2 of Table 4. _Next suppose that r is odd and k = 2, or 3. Then the preimage in Gk(r) of N(2, +), or N(2), is equal to (N(2, +), }, or M(1), respectively. Each of these preimage groups has vertex-orbits Aee U Aoo and Aeo U Aoe in X(r), and hence the normal quotients of (Y(r), H2(r)) modulo N(2, +), and of (Y(r), H3(r)) modulo N(2), are both isomorphic to (K2, Z2). This proves that lines 3 and 4 of Table 4 are valid. Now let (r, G) = (X(r), G3(r)) and (Y, G') = (Y(r), H3(r)). First consider N = J = Then the N-vertex-orbits in r are the sets B, = {(i + j, j) | j e Z2r} for i e Z2r. The quotient (rN, G/N) is the unoriented cycle C2r with edges of both orientations between adjacent N-orbits Bj,Bi+1 (for example, (i, 0) ^ (i + 1,0) and (i, 0) ^ ((i + 1) - 1, -1)). Hence N is the kernel of the G-action on the set of N-orbits, and (rw, G/N) = (C2r,D>4r), as in line 5 of Table 4 for 'N in G3(r)'. The same argument with 2r replaced by s, proves line 5 for 'N in G3Z(s)' with N = J. Continuing with N = J in G3(r), since N contains M(r), it follows from Lemma 2.1 that the normal quotient of (Y, G') modulo N is also (C2r, D4r), completing the proof of line 5 of Table 4. Moreover, if we replace N by J(+) = (^1M2, Mi}, then the N-vertex-orbits become B, U Bi+r, for 0 < i < r, and the quotients (rN, G/N) and (rN, G'/N) both become (Cr, D2r), proving line 7 of Table4. Now consider M = (m1m-1) in G = G3(r). The M-vertex-orbits in r are the sets = {(i + j, -j) | j e Z2r} for i e Z2r. All the out-neighbours of vertices in B, lie in Bi+1, and hence the quotient is (an oriented) cycle of length 2r and the induced group is Z2r. Moreover the element t e G fixes each D, setwise and the kernel of the G-action on the set of M-orbits is N := K = (M, t}. Thus (rw, G/N) = (C2r, ), and since N contains M(r), it follows from Lemma 2.1 that the normal quotient of (Y, G') modulo N is also (C2r, Z2r), as in line 6 of Table 4. If we replace 2r by s and (r, G) by 378 Ars Math. Contemp. 12 (2017) 383-413 (Z(s), G3Z(s)), the argument above proves line 6 for N = K in G3Z(s), completing the proof of line 6 of Table 4. Finally, if we replace N by K(+) = t, ¿1) in G3(r), then the N-vertex-orbits in X(r) become Di U Di+r for 0 < i < r, and the quotients (rN, G/N) and (rN, G'/N) both become (Cr, Zr), as asserted in line 8 of Table 4. □ Theorem 1.3 follows from Lemmas 5.1 and 5.2. 6 Identifying the basic pairs (r, G) for Theorem 1.2 Each of the pairs (r, G) in Theorem 2 lies in OG(4), by Lemma 3.3. Before competing the proof of Theorem 1.2 by determining the basic graph-group pairs, we prove a preliminary lemma. The centraliser of a subgroup N of a group G is the subgroup CG(N) = {g e G | gh = hg, V h e N}. For a prime p, Op(G) is the (unique) largest normal p-subgroup of G. By Sylow's Theorem, Op(G) is contained in every Sylow p-subgroup of G. Possibly Op(G) = 1. Lemma 6.1. Suppose that r > 3. (a) Let N(2) be as in (1.1), a subgroup of G(r). Then CG(r)(N(2)) = (¿1,^2). (b) For t odd, O2(G2(t)) = M(t), O2(G3(t)) = (¿{,¿2), and O2(G3z(t)) = 1. Proof. (a) Let C := CG(r)(N(2)). Recall that N(2) = (¿¡,¿2) and that (^1,^2) is abelian, so (¿1,^2) < C. Let K = (¿1, ¿2,a1,a2). Then each element of G(r) \ K interchanges (¿1) and (¿2), and hence does not centralise N(2). Thus C < K. Similarly, for i = 1, 2, any element of K not lying in (¿1,^2,ai) inverts (¿3-i), so does not lie in C since r > 2. It follows that C = (¿1,^2). (b) Let Q = O2(Gk(t)) with k = 2 or 3. Since M(t) = (¿{¿2) = Z2 is normal in Gk (t), we have M(t) < Q. Moreover, since t is odd, the normal subgroups N(2) (of order t2) and Q intersect in the identity subgroup. Hence Q < CG(t)(N(2)) n Gk(t) = L, say, and by part (a), L = (¿1, ¿2) n Gk(t). In fact Q must be contained in the unique Sylow 2-subgroup P of L. If k = 2, then P = M(t) and hence Q = M(t). If k = 3, then P = (¿[,¿2), and since this subgroup P is a normal 2-subgroup of G3(t), it follows that Q = P. Finally consider Q = O2(G3z(t)). Since IG3Z(t)| = 2t2 with t odd, we have |Q| < 2. Suppose for a contradiction that |Q| = 2. Then Q n N = 1, where N = (¿1,p2) (of odd order t2). So Q centralises N, but this implies that G3Z (t) = NQ is abelian, which is not the case. Hence Q = 1. □ Lemma 6.2. The 'Conditions to be Basic' in Table 2 are correct, namely, (a) (X (r), Gk (r)) is basic if and only if k = 1 and r is an odd prime; (b) (Y (r), Hk (r)) is basic if and only if either r = 2, or k = 2 and r is an odd prime; (c) (Z (s), G3Z (s)) is basic if and only if s is an odd prime. Moreover the 'Basic Type' entries in Table 2 are also correct. Proof. (a) Suppose first that (X(r),Gk(r)) is basic, that is, (X(r),Gk(r)) has no proper nondegenerate normal quotients. It follows from lines 1 and 2 of Table 3 that k = 1 and r is an odd prime. J. A. Al-bar et al.: A normal quotient analysis for some families of oriented four-valent graphs 379 Conversely suppose that k = 1 and r is an odd prime, and assume, for a contradiction that Gi (r) has a nontrivial normal subgroup N such that (X(r)N, Gk (r)/N) is nondegen-erate. Then by [2, Theorem 1.1], N is semiregular on the vertices of X(r), and this quotient has valency 4, so N has at least five vertex-orbits. Without loss of generality we may assume that N is a minimal normal subgroup of G1(r). Now N n N(2) = 1 would imply that N < CGl(r)(N(2)), and hence by Lemma 6.1 that N < (m1,M2) n Gi(r) = N(2), which in turn implies N < N n N(2) = 1, a contradiction. Hence N n N(2) = 1, so by the minimality of N, we have N < N(2). Since N(2) has only four vertex orbits in X(r), N must be a proper subgroup of N(2), and since |N(2)| = r2 and r is an odd prime, it follows that |N| = r. Since N is normalised by t e G1(r), it follows that N = (m2) for i = 1 or i = 2, and hence that N = (m2 m!®) for some i such that 1 < i < r. Now N must contain (m1M2®)t = M2M1®. Since the only element of N projecting to m2® is (M1M2®)®, we have m2m2® = (Mi'M2®)®, and hence m^® -1) = 1, so i2 = 1 (mod r). This implies that i =1 or r - 1. However neither (m2m2) nor (M?M2(r-1)) is normalised by m1 02 e G1(r). This is a contradiction. Therefore (X(r),Gk(r)) is basic when k = 1 and r is an odd prime. Moreover (X (r), G1(r)) is basic of cycle type, see line 1 of Table 4. (b) Suppose next that (r', G') = (Y(r), Hk(r)) is basic, where r is even if k = 1. It follows from lines 4, 5 and 6 of Table 3 that either r = 2, or k = 2 and r is an odd prime. Now we prove the converse. Suppose that r = 2, or k = 2 and r is an odd prime. Let M be a minimal normal subgroup of G' = Hk (r) and consider the quotient r'M. If (rM, G'/M) is nondegenerate (hence of valency 4), then by [2, Theorem 1.1], M is semiregular with at least five vertex-orbits on r', and M is the kernel of the G'-action on the M-orbits. On the other hand if (rM, G'/M) is degenerate, then we replace M by the kernel of the G'-action on the M-orbits. We consider the possibilities for (rM, G'/M): in particular if none are nondegenerate then (r', G') is basic. Suppose first that r = 2. Then the graph r' has only eight vertices, and hence M has at most four vertex-orbits, so all quotients (rM, G'/M) are degenerate. Thus if r = 2, then (r', G') is basic. It is basic of cycle type, by lines 1 and 2 of Table 4. Suppose now that k = 2 and r is an odd prime. Note that the normal subgroup N(2) of G' has just two vertex-orbits, each of size r2, on r'. If M contains N(2) then by the minimality of M, M = N(2, +) (the kernel of the G'-action on the N(2)-orbits) and (rM, G'/M) = (K2, Z2) as in line 4 of Table 4. Suppose now that M 2 N(2). By Lemma2.1, since (r', G') is isomorphic to the normal quotient of (r, G) = (X (r), Gk (r)) modulo the normal subgroup N = M(r) of G (Table 3, line 2), it follows that (rM, G'/M) is isomorphic to a normal quotient (rL, G/L) for some normal subgroup L of G such that N < L and L is the kernel of the G-action on the L-vertex-orbits on r, and G/L = G'/M. Moreover L/N corresponds to M under the isomorphism G ^ G'. In particular, L/N is a minimal normal subgroup of G/N if M is a minimal normal subgroup of G', and since M 2 N(2) we have L 2 N(2). If |L| is not divisible by (the odd prime) r, then L is a normal 2-subgroup of G = G2(r) properly containing N = M(r). Hence L < O2(G) and O2(G) = M(r), contradicting Lemma 6.1(b). Thus |L| is divisible by r. Then L' := L n N(2) = 1, and L' = N(2) since L 2 N(2). Since |N(2)| = r2, it follows that |L'| = r, and, being the intersection of two normal subgroups, L' is normal in G = G2 (r). We argue as in the proof of part (a): L' = (m2) for i = 1 or i = 2 since L' is normalised by tm1. So L' = (m2m2®), for some i such that 1 < i < r. However o2 e G2(r) and o2 does not normalise L', contradiction. Thus there is no proper normal quotient (rM, G'/M) with M 2 N(2). Hence (r', G') is 380 Ars Math. Contemp. 12 (2017) 383-413 basic and its only proper normal quotient is (K2, Z2). This implies that (r', G') is basic of biquasiprimitive type, see Table 1, and completes the proof of part (b). (c) Suppose now that (r, G) = (Z(s),G3Z(s)), where s is odd. If (r, G) is basic then it follows from line 7 of Table 3 that s is an odd prime. Suppose conversely that s is an odd prime. Let M be a nontrivial normal subgroup of G which is equal to the kernel of the G-action on the M-orbits in r, and consider (rM, G/M). If M contains N = N(1) = (of order s2), then since N is vertex-transitive on Z(s), we have M = G and (rM, G/M) = (Ki, 1). So assume that N % M .If M n N =1, then M is a normal subgroup of G of order dividing |G|/|N| = 2, and so |M| = 2 and M < O2(G), contradicting Lemma 6.1. Thus M n N must have order s, and must be normal in G. Since M n N is normalised by t g G, it follows that M n N = that is, M n N is either J or the derived subgroup K' of K, as defined in (1.2). If M n N = K', then the orbits of M n N and K are the same. Thus rM is a quotient of rMnN which, in either case, is a cycle of length s, by lines 5 and 6 of Table 4. Thus (r, G) is basic of cycle type, completing the proof of part (c). □ Finally we observe that Theorem 1.2 follows from Lemma 3.3 (for membership in OG(4)), and Lemma 6.2. References [1] J. A. Al-bar, A. N. Al-kenani, N. M. Muthana and C. E. Praeger, Finite edge-transitive oriented graphs of valency four with cyclic normal quotients, J. Algebraic Combin. (to Appear), https://arxiv.org/abs/1612.0 602 4. [2] J. A. Al-bar, A. N. Al-kenani, N. M. Muthana, C. E. Praeger and P. Spiga, Finite edge-transitive oriented graphs of valency four: a global approach, Electron. J. Combin. 23 (2016), Paper 1.10, 23. [3] P. J. Cameron, Permutation Groups, volume 45 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 1999, doi:10.1017/CB09780511623677. [4] M. D. E. Conder, P. Potocnik and P. Sparl, Some recent discoveries about half-arc-transitive graphs, Ars Math. Contemp. 8 (2015), 149-162. [5] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9. [6] A. Hujdurovic, K. Kutnar and D. Marusic, Half-arc-transitive group actions with a small number of alternets, J. Combin. TheorySer.A 124 (2014), 114-129, doi:10.1016/j.jcta.2014.01.005. [7] D. Marusic, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B 73 (1998), 41-76, doi:10.1006/jctb.1997.1807. [8] D. Marusic, Recent developments in half-transitive graphs, Discrete Math. 182 (1998), 219231, doi:10.1016/S0012- 365X(97)00142- 8. [9] D. Marusic and R. Nedela, Maps and half-transitive graphs of valency 4, European J. Combin. 19 (1998), 345-354, doi:10.1006/eujc.1998.0187. [10] D. Marusic and C. E. Praeger, Tetravalent graphs admitting half-transitive group actions: alternating cycles, J. Combin. Theory Ser. B 75 (1999), 188-205, doi:10.1006/jctb.1998.1875. [11] D. Marusic and P. Sparl, On quartic half-arc-transitive metacirculants, J. Algebraic Combin. 28 (2008), 365-395, doi:10.1007/s10801-007-0107-y. J. A. Al-bar et al.: A normal quotient analysis for some families of oriented four-valent graphs 381 [12] D. Marušič and A. O. Waller, Half-transitive graphs of valency 4 with prescribed attachment numbers, J. Graph Theory 34 (2000), 89-99, doi:10.1002/(SICI)1097-0118(200005)34:1 (89:: AID-JGT8)3.0.CO;2-K. [13] P. Potočnik, 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.