/^creative ^commor ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 8 (2015) 133-148 A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two Dedicated to Dragan Marusic on the occasion of his 60th birthday PrimoZ Potocnik * Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia affiliated also with: IAM, University of Primorska, Muzejski trg 2, SI-6000 Koper, Slovenia and with: IMFM, Jadranska 19, SI-1000 Ljubljana, Slovenia Pablo Spiga Dipartimento di Matematica Pura e Applicata, University ofMilano-Bicocca, Via Cozzi 53, 20126 Milano, Italy Gabriel Verretf Centre for Mathematics of Symmetry and Computation, The University of Western Australia, 35 Stirling Highway, Crawley, WA 6009, Australia and FAMNIT, University of Primorska, Glagoljaska 8, SI-6000 Koper, Slovenia Received 18 October 2013, accepted 6 June 2014, published online 22 September 2014 Abstract A complete list of all connected arc-transitive asymmetric digraphs of in-valence and out-valence 2 on up to 1000 vertices is presented. As a byproduct, a complete list of all connected 4-valent graphs admitting a 1 -arc-transitive group of automorphisms on up to 1000 vertices is obtained. Several graph-theoretical properties of the elements of our census are calculated and discussed. Keywords: Graph, digraph, edge-transitive, vertex-transitive, arc-transitive, half-arc-transitive. Math. Subj. Class.: 05E18, 20B25 * Supported by Slovenian Research Agency, projects L1-4292 and P1-0222. t Supported by UWA as part of the Australian Research Council grant DE130101001. E-mail addresses: primoz.potocnik@fmf.uni-lj.si (Primož Potocnik), pablo.spiga@unimib.it (Pablo Spiga), gabriel.verret@uwa.edu.au (Gabriel Verret) ©® This work is licensed under http://creatrvecommons.org/licenses/by/3.0/ 134 Ars Math. Contemp. 8 (2015) 133-148 1 Introduction Recall that a graph r is called 1 -arc-transitive provided that its automorphism group Aut(r) acts transitively on its edge-set E(T) and on its vertex-set V(T) but intransitively on its arc-set A(r). More generally, if G is a subgroup of Aut(r) such that G acts transitively on E(r) and V(r) but intransitively on A(r), then G is said to act 1 -arc-transitively on r and we say that r is (G, 1 )-arc-transitive. To shorten notation, we shall say that a 2-arc-transitive graph is a HAT and that a graph admitting a 1 -arc-transitive group of automorphisms is a GHAT. Clearly, any HAT is also a GHAT. Conversely, a GHAT is either a HAT or arc-transitive. The history of GHATs goes back to Tutte who, in his 1966 paper [38, 7.35, p.59], proved that every GHAT is of even valence and asked whether HATs exist at all. The first examples of HATs were discovered a few years later by Bouwer [6]. After a short break, interest in GHATs picked up again in the 90s, largely due to a series of influential papers of Marusic concerning the GHATs of valence 4 (see [1, 17, 21, 24], to list a few). For a nice survey of the topic, we refer the reader to [16], and for an overview of some more recent results, see [13, 22]. To shorten notation further, we shall say that a connected GHAT (HAT, respectively) of valence 4 is a 4-GHAT (4-HAT, respectively). The main result of this paper is a compilation of a complete list of all 4-GHATs with at most 1000 vertices. This improves an unpublished work [23], where all 4-HATs of order up to 869 vertices (with the exception of order 512) with the vertex-stabiliser of order 2 were determined. Our result was obtained indirectly using an intimate relation between 4-GHATs and connected arc-transitive asymmetric digraphs of in- and out-valence 2 (we shall call such digraphs 2-ATDs for short) - see Section 2.2 for details on this relationship. These results can be succinctly summarised as follows: Theorem 1.1. There are precisely 26457 pairwise non-isomorphic 2-ATDs on at most 1000 vertices, and precisely 11941 4-GHATs on at most 1000 vertices, of which 8695 are arc-transitive and 3246 are 2 -arc-transitive. The actual lists of (di)graphs, together with a spreadsheet (in a "comma separated values" format) with some graph theoretical invariants, is available at [28]. The rest of this section is devoted to some interesting facts gleaned from these lists. All the relevant definitions that are omitted here can be found in Section 2. In Section 3, we explain how the lists were computed and present the theoretical background which assures that the computations were exhaustive. In Section 4, information about the format of the files available on [28] is given. We now proceed with a few comments on the census of 4-HATs. By a vertex-stabiliser of a vertex-transitive graph or digraph r, we mean the stabiliser of a vertex in Aut(r). Even though it is known that a vertex-stabiliser of a 4-HAT can be arbitrarily large (see [18]), not many examples of 4-HATs with vertex-stabilisers of order larger than 2 were known, and all known examples had a very large number of vertices. Recently, Conder and Sparl (see also [8]) discovered a 4-HAT on 256 vertices with vertex-stabiliser of order 4 and proved that this is the smallest such example. This fact is confirmed by our census; in fact, the following theorem can be deduced from the census. Theorem 1.2. Amongst the 3246 4-HATs on at most 1000 vertices, there are seventeen with vertex-stabiliser of order 4, three with vertex-stabiliser of order 8, and none with P. Potočnik et al.: A census of 4-valent half-arc-transitive graphs. 135 larger vertex-stabilisers. The smallest 4-HAT with vertex-stabiliser of order 4 has order 256 and the smallest two with vertex-stabilisers of order 8 have 768 vertices; the third 4-HATwith vertex-stabiliser of order 8 has 896 vertices. Another curiosity about 4-HATs is that those with a non-abelian vertex-stabiliser tend to be very rare (at least amongst the "small" graphs). The first known 4-HAT with a non-abelian vertex-stabiliser was discovered by Conder and Marusic (see [7]) and has 10752 vertices. Further examples of 4-HATs with non-abelian vertex-stabilisers were discovered recently (see [8]), including one with a vertex-stabiliser of order 16. However, the one on 10752 vertices remains the smallest known example. Using our list, the following fact is easily checked. Theorem 1.3. Every 4-HATwith a non-abelian vertex-stabiliser has more than 1000 vertices. In fact, there are strong indications that the graph on 10752 vertices discovered by Conder and Marussics is the smallest 4-HAT with a non-abelian vertex-stabiliser. We will call a 4-HAT with a non-solvable automorphism group a non-solvable 4-HAT. The first known non-solvable 4-HAT was constructed by Marusic and Xu [24]; and its order is 7!/2. An infinite family of non-solvable 4-HATs were constructed later by Malnic and Marusic [15]. The smallest member of this family has an even larger order, namely 11!/2. To the best of our knowledge, no smaller non-solvable 4-HATs appeared in literature. Perhaps surprisingly, small examples of non-solvable 4-HATs seem not to be too rare, as can be checked from our census (as well as from the unpublished work [23]). Theorem 1.4. There are thirty-two non-solvable 4-HATs with at most 1000 vertices. The smallest one, named HAT[480,44], has order 480, girth 5, radius 5, attachment number 2, alter-exponent 2, and alter-perimeter 1. It is non-Cayley and non-bipartite. (The terms radius, attachment number, alter-exponent, and alter-perimeter appearing in the statement of Theorem 1.4 are defined in Sections 4.2 and 4.3.) Let us now continue with a few comments on the census of 2-ATDs. All the undefined notions mentioned in the theorems below are explained in Sections 2, 4.2 and 4.3. It is not surprising that, apart from the generalised wreath digraphs (see Section 2.3 for the definition), very few of the 2-ATDs on at most 1000 vertices are 2-arc-transitive. In fact, the following can be deduced from the census. Theorem 1.5. Out of the 26457 2-ATDs on at most 1000 vertices, 961 are generalised wreath digraphs. Of the remaining 25496, only 1199 are 2-arc-transitive (the smallest having order 18), only 255 are 3-arc-transitive (the smallest having order 42), only 61 are 4-arc-transitive (the smallest having order 90), and only 6 are 5-arc-transitive (the smallest two having order 640); none ofthem is 6-arc-transitive. Note that the non-existence of a 6-arc-transitive non-generalised-wreath 2-ATD on at most 1000 vertices follows from a more general result (see Corollary 3.2). Recall that there is no 4-HAT on at most 1000 vertices with a non-abelian vertex-stabiliser (Theorem 1.3). Consequently (see Section 2.2), every 2-ATD on at most 1000 vertices with a non-abelian vertex-stabiliser has an arc-transitive underlying graph; and there are indeed such examples. In fact, the following holds (see Section 2.1 for the definition of self-opposite). 136 Ars Math. Contemp. 8 (2015) 133-148 Theorem 1.6. There are precisely forty-five 2-ATDs on at most 1000 vertices with a non-abelian vertex-stabiliser. They are all self-opposite, at least 3-arc-transitive, have non-solvable automorphism groups, and radius 3. The smallest of these digraphs has order 42, and the smallest that is 4-arc-transitive has order 90. There are no 5-arc-transitive 2-ATDs with a non-abelian vertex-stabiliser and order at most 1000. If a 2-ATD is self-opposite, then the isomorphism between the digraph and its opposite digraph is an automorphism of the underlying graph, making the underlying graph arc-transitive. Hence, self-opposite 2-ATDs always yield arc-transitive 4-GHATs. However, the converse is not always true: there are 2-ATDs that are not self-opposite, but have an arc-transitive underlying graph. In this case, the index of the automorphism group of the 2-ATD in the automorphism group of its underlying graph must be larger than 2 (for otherwise the former would be normal in the latter and thus any automorphism of the underlying graph would either preserve the arc-set of the digraph, or map it to the arc-set of the opposite digraph). It is perhaps surprising that there are not many small examples of such behaviour. Theorem 1.7. There are precisely fifty-two 2-ATDs on at most 1000 vertices that are not self-opposite but have an arc-transitive underlying graph. The smallest two have order 21. None of these digraphs is 2-arc-transitive. The index of the automorphism group of these digraphs in the automorphism group of the underlying graphs is always 8. We finish this section by mentioning an earlier attempt of Stephen Wilson and the first author of this paper to compile a census of all small edge-transitive graphs of valence 4, and thus, in particular, of all 4-GHATs; see [31]. The results of this paper confirm that the list given in [31] contains all 4-GHATs of order at most 100. 2 Notation and definitions 2.1 Digraphs and graphs A digraph is an ordered pair (V, A) where V is a finite non-empty set and A C V x V is a binary relation on V. We say that (V, A) is asymmetric if A is asymmetric, and we say that (V, A) is a graph if A is irreflexive and symmetric. If r = (V, A) is a digraph, then we shall refer to the set V and the relation A as the vertex-set and the arc-set of r, and denote them by V(r) and A(r), respectively. Members of V and A are called vertices and arcs, respectively. If (u, v) is an arc of a digraph r, then u is called the tail, and v the head of (u, v). If r is a graph, then the unordered pair {u, v} is called an edge of r and the set of all edges of r is denoted E(r). If r is a digraph, then the opposite digraph ropp has vertex-set V(r) and arc-set {(v, u) : (u, v) € A(r)}. The underlying graph of r is the graph with vertex-set V(r) and with arc-set A(r) U A(ropp). A digraph is called connected provided that its underlying graph is connected. Let v be a vertex of a digraph r. Then the out-neighbourhood of v in r, denoted by r+(v), is the set of all vertices u of r such that (v, u) € A(r), and similarly, the in-neighbourhood r-(v) is defined as the set of all vertices u of r such that (u, v) € A(r). Further, we let val+(v) = |r+(v)| and val-(v) = |r-(v)| be the out-valence and invalence of r, respectively. If there exists an integer r such that val+(v) = val-(v) = r for every v € V(r), then we say that r is regular of valence r, or simply that r is an r-valent digraph. P. Potočnik et al.: A census of 4-valent half-arc-transitive graphs. 137 An s-arc of a digraph r is an (s + 1)-tuple (v0, vi,..., vs) of vertices of r, such that (vi-1, vj) is an arc of r for every i e {1,..., s} and vi-1 = vi+1 for every i e {1,..., s — 1}. If x = (v0, v1,..., vs) is an s-arc of r, then every s-arc of the form (v1, v2,..., vs, w) is called a successor of x. An automorphism of a digraph r is a permutation of V(r) which preserves the arc-set A(r). Let G be a subgroup of the full automorphism group Aut(r) of r. We say that r is G-vertex-transitive or G-arc-transitive provided that G acts transitively on V(r) or A(r), respectively. Similarly, we say that r is (G, s)-arc-transitive if G acts transitively on the set of s-arcs of r. If r is a graph, we say that it is G-edge-transitive provided that G acts transitively on E(r). When G = Aut(r), the prefix G in the above notations is usually omitted. If r is a digraph and v e V(r), then a v-shunt is an automorphism of r which maps v to an out-neighbour of v. 2.2 From 4-GHATs to 2-ATDs and back If r is a connected 4-valent (G, 2 )-arc-transitive graph, then G has two paired orbits on the arc-set of r, each orbit having the property that each vertex of r is the head of precisely two arcs, and also the tail of precisely two arcs of the orbit. By taking any of these two orbits as an arc-set of a digraph on the same vertex-set, one thus obtains a 2-ATD whose underlying graph is r, and admitting G as an arc-transitive group of automorphisms. Conversely, the underlying graph of a G-arc-transitive 2-ATD is a (G, 2 )-arc-transitive 4-GHAT. In this sense the study of 4-GHATs is equivalent to the study of 2-ATDs. In Section 3, we explain how a complete list of all 2-ATDs on at most 1000 vertices was obtained. The above discussion shows how this yields a complete list of all 4-GHATs on at most 1000 vertices. 2.3 Generalised wreath digraphs Let n be an integer with n > 3, let V = Zn x Z2, and let A = {((i, a), (i + 1, b)) : i e Zn, a, b e Z2}. The asymmetric digraph (V, A) is called a wreath digraph and denoted by W n. If r is a digraph and r is a positive integer, then the r-th partial line digraph of r, denoted Plr (r), is the digraph with vertex-set equal to the set of r-arcs of r and with (x, y) being an arc of Plr (r) whenever y is a successor of x. If r = 0, then we let Plr (r) = r. Let r be a positive integer. The (r — 1)-th partial line digraph Plr-1(Wn) of the wreath digraph Wn is denoted by W(n, r) and called a generalised wreath digraph. Generalised wreath digraphs were first introduced in [32], where W(n, r) was denoted Cn(2,r). It was proved there that Aut(W(n, r)) = C2 I Cn = x Cn and that Aut(WV(n, r)) acts transitively on the (n—r)-arcs but not on the (n — r +1)-arcs of W(n, r) [32, Theorem 2.8]. In particular, W (n, r) is arc-transitive if and only if n > r + 1. Note that |V(W (n, r))| = n2r, and thus |Aut(W(n,r))v | = n2n/n2r = 2n-r. The underlying graph of a generalised wreath digraph will be called a generalised wreath graph. 138 Ars Math. Contemp. 8 (2015) 133-148 2.4 Coset digraphs Let G be a group generated by a core-free subgroup H and an element g with g-1 G HgH. One can construct the coset digraph, denoted Cos(G, H, g), whose vertex-set is the set G/H of right cosets of H in G, and where (Hx, Hy) is an arc if and only if yx-1 G HgH. Note that the condition g-1 G HgH guarantees that the arc-set is an asymmetric relation. Moreover, since G = (H, g), the digraph Cos(G, H, g) is connected. The digraph Cos(G, H, g) is G-arc-transitive (with G acting upon G/H by right multiplication), and hence Cos(G, H, g) is a G-arc-transitive and G-vertex-transitive digraph with g being a v-shunt (where v = H • 1 G G/H). On the other hand, it is folklore that every such graph arises as a coset digraph. Lemma 2.1. If r is a connected G-arc-transitive and G-vertex-transitive digraph, v is a vertex of r, and g is a v-shunt contained in G, then r = Cos(G, Gv, g). 3 Constructing the census If r is a G-vertex-transitive digraph with n vertices, then |G| = n|Gv |. If one wants to use the coset digraph construction to obtain all 2-ATDs on n vertices, one thus needs to consider all groups G of order n|Gv | that can act as arc-transitive groups of 2-ATDs. In order for this approach to be practical, two issues must be resolved: First, one must get some control over |G| and thus over |Gv |. (Recall that in W(n, r), |Gv | can grow exponentially with |V(W(n, r))|, as n ^ to and r is fixed). Second, one must obtain enough structural information about G to be able to construct all possibilities. Fortunately, both of these issues were resolved successfully. The problem of bounding |Gv | was resolved in a recent paper [37] and details can be found in Section 3.1. The second problem was dealt with in [19], and later, in greater generality in [30] (both of these papers rely heavily on a group-theoretical result of Glauberman [12]); the summary of relevant results is given in Section 3.2. 3.1 Bounding the order of the vertex-stabiliser The crucial result that made our compilation of a complete census of all small 2-ATDs possible is Theorem 3.1, stated below, which shows that the generalised wreath digraphs (defined in Section 2.3) are very special in the sense of having large vertex-stabilisers. In fact, together with the correspondence described in Section 2.2, [37, Theorem 9.2] has the following corollary: Theorem 3.1. Let r be a G-arc-transitive 2-ATD on at most m vertices and let t be the largest integer such that m > t2*+2. Then one of the following occurs: 1. r = W(n, r) for some n > 3 and 1 < r < n — 1, 2. |Gv |< max{16, 2*}, 3. (r, G) appears in the last line of [37, Table 1]. In particular, |V(r)| = 8100. The following is an easy corollary: Corollary 3.2. Let r be a G-arc-transitive 2-ATD on at most 1000 vertices. Then either |Gv | < 32 or r = W(n, r) for some n > 3 and 1 < r < n — 1. P. Potočnik et al.: A census of 4-valent half-arc-transitive graphs. 139 3.2 Structure of the vertex-stabiliser Definition 3.3. Let s and a be positive integers satisfying | s < a < s, and let c be a function assigning a value citj G {0,1} to each pair of integers i, j with a < j < s - 1 and 1 < i < 2a - 2s + j + 1. Let Aj,a be the group generated by {x0, xi,..., xs_i, g} and subject to the defining relations: • - yv»2 — - yv»2 — 1 • Xo — Xi — • • • — Xj_i — 1, • xg — xi+i for i G {0,1,..., s - 2}; • if j < a, then [x0, xj] — 1; • if j > a, then [xo, xj ] — xjj x^i • • • xC_T+2;+j+1j. Furthermore, let As,a be the family of all groups Aj,a for some c. It was proved in [19] (see also [30]) that every group G acting arc-transitively on a 2-ATD is isomorphic to a quotient of some Aj,a. More precisely, the following can be deduced from [19] or [30]. Theorem 3.4. Let r be a G-arc-transitive 2-ATD, let v G V(r) and let s be the largest integer such that G acts transitively on the set of s-arcs of r. Then there exists an integer a satisfying | s < a < s, a function c as in Definition 3.3, and an epimorphism p: Aj,a — G, which maps the group (x0,..., xs_i} isomorphically onto Gv and the generator g to some v-shunt in G. In particular, |Gv | — 2s. In this case, we will say that (r, G) is of type Aj a, and call the group Aj a the universal group of the pair (r, G). For s, a, and a function c satisfying the conditions of Definition 3.3, let c' be the function defined by ci,j — c2a_2S+j+2 _ i,j. The relationship between c and c' can be visualised as follows: if one fixes the index j and views the function i i—y ci,j as the sequence [ci,j, c2,j,..., c2a_2s+j+ijj], then the sequence for c' is obtained by reversing the one for c. If G — Aj,a then we denote the opposite type Aj,a by Gopp. Observe that if (r, G) is of type G, then (ropp, G) is of typeGopp. A class of groups, obtained from As,a by taking only one group in each pair {(5, Gopp}, G G As,a, will be denoted Aj^. (Note that some groups G might have the property that G — Gopp.) In view of Corollary 3.2, we shall be mainly interested in the universal groups Aj,a with s < 5 (as, excluding generalised wreath digraphs, these are the only types of 2-ATDs of order at most 1000). We list the relevant classes Ajed for s < 5 explicitly in Table 1. Groups in Aj^, for a fixed s will be named by Aj, where i will be a positive integer, where groups with larger a will be indexed with lower i. Also, the generators x0, xi, x2, x3, and x4 will be denoted a, b, c, d, and e, respectively. 3.3 The algorithm and its implementation We now have all the tools required to present a practical algorithm that takes an integer m as input and returns a complete list of all 2-ATDs on at most m vertices (see Algorithm 1). It is based on the fact that every such digraph can be obtained as a coset digraph of some group G (see Lemma 2.1), and that G is in fact an epimorphic image of some group Aj,a (see Theorem 3.4) with Gv and the shunt being the corresponding images of (x0,..., x8 _ i} and g in Aj,a. Moreover, if r is not a generalised wreath digraph or the exceptional digraph on 8100 vertices mentioned in part 3 of Theorem 3.1, then the parameter s satisfies s2j+2 < m, and 140 Ars Math. Contemp. 8 (2015) 133-148 name G (a,g | a2) A2 (a,b,g | a2, b2, agb, [a,b]) A3 (a,b,c,g | a2,b2, c2, agb,bgc, [a,b], [a,c]) A coto (a, b, c, g | a2, b2, c2, agb,bgc, [a,b], [a,c]b) A4 (a, b, c, d, g | a2, b2, c2, d2, agb, bgc, cgd, [a, b], [a, c], [a, d]) A4 (a, b, c, d, g | a2, b2, c2, d2, agb, bgc, cgd, [a, b], [a, c], [a, d]b) A4 (a, b, c, d, g | a2, b2, c2, d2, agb, bgc, cgd, [a, b], [a, c], [a, d]bc) A1 (a, b, c, d, e, g | a2, b2, c2, d2, e2, d2, agb,bgc, cgd,dge, [a,b], [a,c], [a,d], [a,e]) A5 (a, b, c, d, e, g | a2, b2, c2, d2, e2, d2, agb, bgc, cgd, dge, [a, b], [a, c], [a, d], [a, e]b) A5 (a, b, c, d, e, g | a2, b2, c2, d2, e2, d2, agb, bgc, cgd, dge, [a, b], [a, c], [a, d], [a, e]c) A5 (a, b, c, d, e, g | a2, b2, c2, d2, e2, d2, agb, bgc, cgd, dge, [a, b], [a, c], [a, d], [a, e]bc) A5 (a, b, c, d, e, g | a2,b2, c2, d2, e2, d2, agb,bgc, cgd,dge, [a,b], [a,c], [a,d], [a,e]bd) A5 (a, b, c, d, e, g | a2, b2, c2, d2, e2, d2, agb, bgc, cgd, dge, [a, b], [a, c], [a, d], [a, e]bcd) Table 1: Universal groups of 2-ATDs with |Gv | < 32 the order of the epimorphic image G is bounded by 2s m (see Theorem 3.1). The algorithm thus basically boils down to the task of finding normal subgroups of bounded index in the finitely presented groups AS,a. Practical implementations of this algorithm have several limitations. First, the best known algorithm for finding normal subgroups of low index in a finitely presented group is an algorithm due to Firth and Holt [11]. The only publicly available implementation is the LowlndexNormalSubgroups routine in Magma [5] and the most recent version allows one to compute only the normal subgroups of index at most 5 • 105; hence only automorphisms groups of order 5 • 105 can possibly be obtained in this way. More importantly, even when only normal subgroups of relatively small index need to be computed, some finitely presented groups are computationally difficult. For example, finding all normal subgroups of index at most 2048 of the group A} = C2 * seems to represent a considerable challenge for the LowlndexNormalSubgroups routine in Magma. In order to overcome this problem, we have used a recently computed catalogue of all (2, *)-groups of order at most 6000 [29], where by a (2, *)-group we mean any group generated by an involution x and one other element g. Since A} is a (2, *)-group and every non-cyclic quotient of a (2, *)-group is also a (2, *)-group, this catalogue can be used to obtain all the quotients of A } of order up to 6000. Consequently, all 2-ATDs admitting an arc-regular group of automorphisms of order at most 3000 can be obtained. Similarly, since A} is also a (2, *)-group, we can use this catalogue to obtain all the 2-ATDs of order at most 1500 admitting an arc-transitive group G with |Gv | =4. It should be mentioned that the concept of a (2, *) -group is equivalent to that of a rotary map, that can be described as groups generated by two elements the product of which is P. Potočnik et al.: A census of 4-valent half-arc-transitive graphs. 141 Algorithm 1 2-ATDs on at most m vertices. Require: positive integer m Ensure: D = {r : r is 2-ATD, |V(r)| < m} Let t be the largest integer such that m > t2i+2; Let D be the list of all arc-transitive generalised wreath digraphs on at most m vertices; If m > 8100, add to D the exceptional digraph r on 8100 vertices, mentioned in part 3 of Theorem 3.1; for s € {1,..., max{4, t}} do for a € {[ §s], [ 2 s] + 1,...,s} do for G € AS^ do Let N be the set of all normal subgroups of G of index at most 2s m; for N € N do Let G := G/N and let p: G ^ G be the quotient projection; Let H := p((xo,... ,Xs_i)); if H is core-free in G and |H| = 2s and p(g)-1 € Hp(g)H then Let C := cos(G, H, p); for r € {C, C°pp} do if r is not isomorphism to any of the digraphs in D then add r to the list D; end if end for end if end for end for end for end for 142 Ars Math. Contemp. 8 (2015) 133-148 an involution. A catalogue of all (2, *)-groups of order at most 2000 could thus be derived from Conder's catalogue of rotary maps with at most 1000 edges [9]. Conversely, the catalogue of (2, *)-group of order up to 6000 [29] extends the list in [9] up to 3000 edges in the orientable case and to 1500 in the non-orientable case. Like A} and the groups with (x0,..., xs-\) abelian (namely those with a = s and Oi,j = 0 for all i, j) are also computationally very difficult. One can make the task easier by dividing it into cases, where the order of g is fixed in each case. Since g represents a shunt, it can be proved that its order cannot exceed the order of the digraph (see, for example, [27, Lemma 13]). Cases can then be run in parallel on a multi-core computer. 4 The census and accompanying data Using Algorithm 1, we found that there are exactly 26457 2-ATDs of order up to 1000. Following the recipe explained in Section 2.2, we have also computed all the 4-GHATs, which we split in two lists: 4-HATs and arc-transitive 4-GHATs. The data about these graphs, together with Magma code that generates them, is available on-line at [28]. The package contains ten files. The file "Census-ATD-1k-README.txt" is a text file containing information similar to the information in this section. The remaining nine files come in groups of three, one group for each of the three lists (2-ATDs, arc-transitive 4-GHATs, 4-HATs). In each group, there is a *.mgm file, a *.txt file and a *.csv file. The *.mgm file contains Magma code that generates the corresponding digraphs. After loading the file in Magma, a double sequence is generated (named either ATD, GHAT, or HAT, depending on the file). The length of each double sequence is 1000 and the n-th component of the sequence is the sequence of all the corresponding digraphs of order n, with the exception of the generalised wreath digraphs. Thus, ATD[32,2] will return the second of the four non-generalised-wreath 2-ATDs on 32 vertices (the ordering of the digraphs in the sequence ATD[32] is arbitrary). In order to include the generalised wreath digraphs into the corresponding sequence, one can call the procedure AddGWD( ^ATD,GWD) in the case of the 2-ATDs, or AddGWG(~GHAT,GWG) in the case of the 4-GHATs (note that a generalised wreath graph is never 2-arc-transitive). The *.txt file contains the list of neighbours of each digraph. This file is needed when the *.mgm file is loaded into Magma, but, being an ASCII file, it can be used also by other computer systems to reconstruct the digraphs. For the details of the format, see the "README" file. Finally, the *.csv file is a "comma separated values" file representing a spreadsheet containing some precomputed graph invariants. We shall first introduce some of these invariants and then discuss each *.csv separately. 4.1 Walks and cycles Let r be a digraph. A walk of length n in r is an (n + 1)-tuple (v0, v},..., vn) of vertices of r such that, for any i G {1,... n}, either (vi_i, vi) or (vi, vi_i) is an arc of r. The walk is closed if v0 = vn and simple if the vertices vi are pairwise distinct (with the possible exception of the first and the last vertex when the walk is closed). A closed simple walk in r is called a cyclet. The inverse of a cyclet (v0,..., vn-1, v0) is the cyclet (v0, vn-1,..., v}, v0), and a cyclet (v0,..., vn-1, v0) is said to be a shift of a cyclet (u0,..., un-1, u0) provided that there exists k G Zn such that ui = vi+k for all P. Potočnik et al.: A census of 4-valent half-arc-transitive graphs. 143 i G Zn. Two cyclets W and U are said to be congruent provided that W is a shift of either U or the inverse of U. The relations of "being a shift of" and "being congruent to" are clearly equivalence relations, and their equivalence classes are called oriented cycles and cycles, respectively. With a slight abuse of terminology, we shall sometimes identify a (oriented) cycle with any of its representatives. 4.2 Alter-equivalence, alter-exponent, alter-perimeter, and alter-sequence Let r be an asymmetric digraph. The signature of a walk W = (v0, v\,..., vn) is an n-tuple (e1,e2,..., en), where ej = 1 if (vj_i, vj) is an arc of r, and ej = -1 otherwise. The signature of a walk W will be denoted by 0 such that Ae = Ae+1 (and then Ae = ATO). The smallest such integer is called the alter-exponent of r and denoted by exp(r). The number of equivalence classes of is called the alter-perimeter of r. The name originates from the fact that the quotient digraph of r with respect to is either a directed cycle or the complete graph K2 or the graph K1 with one vertex. If e is the alter-exponent of a (vertex-transitive) digraph r, then the finite sequence [|A1(v)|, |A2 (v) |,..., |Ae(v)|] is called the alter-sequence of r. Several interesting properties of the alter-exponent can be proved (see [20] for example). For example, if r is connected and G-vertex-transitive, then exp(r) is the smallest positive integer e such that the setwise stabiliser GAe(v) is normal in G. The group GAe(v) is the group generated by all vertex-stabilisers in G and G/Gab(v) is a cyclic group. All notions defined in this section for digraphs generalise to half-arc-transitive graphs, where instead of the graph one of the two natural arc-transitive digraphs are considered. As was shown in [20], all the parameters defined here remain the same if instead of a digraph, its opposite digraph is considered. The notions defined in this section were later generalised in the context of infinite digraphs [14]. 4.3 Alternating cycles - radius and attachment number A walk W in an asymmetric digraph is called alternating if its tolerance is either [0,1] or [-1,0] (that is, if the signs in its signature alternate). Similarly, a cycle is called alternating provided that any (and thus every) of its representatives is an alternating walk. This notion was introduced in [17] and used to classify the so-called tightly attached 4-GHATs and 4-HATs of odd radius. The concept of alternating cycles was explored further in a number of papers on 4-HATs (see for example [21, 34]). Let r be a 2-ATD, let C be the set of all alternating cycles of r, and let G = Aut(r). The set C is clearly preserved by the action of G upon the cycles of r. Moreover, since r is arc-transitive, G acts transitively on C. In particular, all the alternating cycles of r are of 144 Ars Math. Contemp. 8 (2015) 133-148 equal length. Half of the length of an alternating cycle is called the radius of r. Since r is 2-valent, every vertex of r belongs to precisely two alternating cycles. It thus follows from vertex-transitivity of r that any (unordered) pair of intersecting cycles can be mapped to any other such pair, implying that there exists a constant a such that any two cycles meet either in 0 or in a vertices. The parameter a is then called the attachment number of r. In general, the attachment number divides the length of the alternating cycle (twice the radius), and there are digraphs where a equals this length; they were classified in [17, Proposition 2.4], where it was shown that their underlying graphs are always arc-transitive. A 2-valent asymmetric digraph with attachment number a is called tightly attached if a equals the radius, is called antipodally attached if a = 2, and is called loosely attached if a =1. Note that tightly attached 2-ATDs are precisely those with alter-exponent 1. 4.4 Consistent cycles Let r be a graph and let G < Aut(T). A (oriented) cycle C in a graph r is called G-consistent provided that there exists g G G that preserves C and acts upon it as a 1-step rotation. A G-orbit of G-consistent oriented cycles is said to be symmetric if it contains the inverse of any (and thus each) of its members, and is chiral otherwise. Consistent oriented cycles were first introduced by Conway in a public lecture [10] (see also [3,25, 26]). Conway's original result states that in an arc-transitive graph of valence d, the automorphism group of the graph has exactly d - 1 orbits on the set of oriented cycles. In particular, if r is 4-valent and G-arc-transitive, then there are precisely three G-orbits of G-consistent oriented cycles. Since chiral orbits of G-consistent cycles come in pairs of mutually inverse oriented cycles, this implies that there must be at least one symmetric orbit, while the other two are either both chiral or both symmetric. Conway's result was generalised in [4] to the case of 1 -arc-transitive graphs by showing that if r is a 4-valent (G, 1 )-arc-transitive graph, then there are precisely four G-orbits of G-consistent oriented cycles, all of them chiral. These four orbits of oriented cycles thus constitute precisely two G-orbits of G-consistent (non-oriented) cycles. 4.5 Metacirculants A weak metacirculant is a graph whose automorphism group contains a vertex-transitive metacyclic group G, generated by p and a, such that the cyclic group (p) is semiregular on the vertex-set of the graph, and is normal in G. This notion was introduced by Marusic and Sparl [22] and generalises that of a metacirculant introduced by Alspach and Parsons [2]. Metacirculants admitting 2-arc-transitive groups of automorphisms were first investigated in [33]. Recently, the interesting problem of classifying all 4-HATs that are weak metacirculants was considered in [22, 35, 36]. Such 4-HATs fall into four (not necessarily disjoint) classes (called Class I, Class II, Class III, and Class IV), depending on the structure of the quotient by the orbits of the semiregular element p. For a precise definition of the class of a 4-HAT weak metacirculant see, for example, [35, Section 2]. Since a given 4-HAT may admit several vertex-transitive metacyclic groups, a fixed graph can fall into several of these four classes. Several interesting facts about 4-HAT (weak) metacirculants are known. For example, tightly attached 4-HATs are precisely the 4-HATs that are weak metacirculants of Class I. P. Potočnik et al.: A census of 4-valent half-arc-transitive graphs. 145 4.6 The data on 2-ATDs The "Census-ATD-1k-data.csv" file concerns 2-ATDs. Each line of the file represents one of the digraphs in the census, and has 19 fields described below. Since this file is in "csv" format, every occurrence of a comma in a field is substituted with a semicolon. • Name: the name of the digraph (for example, ATD[32,2]); • | v| : the order of the digraph; • SelfOpp: contains "yes" if the digraph is isomorphic to its opposite digraph and "no" otherwise; • Opp: the name of the opposite digraph (the same as "Name" if the digraph is self-opposite); • IsUndAT: "yes" if the underlying graph is arc-transitive, "no" otherwise; • UndGrph: the name of the underlying graph, as given in the files "Census-HAT-lk-data.csv" and "Census-GHAT-1k-data.csv" - if the underlying graph is generalized wreath, then this is indicated by, say, "GWD(m,k)" where m and k are the defining parameters. • s: the largest integer s, such that the digraph is s-arc-transitive; • GvAb: "Ab" if the vertex-stabiliser in the automorphism group of the digraph is abelian, otherwise "n-Ab"; • |Tv:Gv|: the index of the automorphism group G of the digraph in the smallest arc-transitive group T of the underlying graph that contains G - if there's no such group T,then 0; • |Av:Gv|: the index of the automorphism group of the digraph in the automorphism group of the underlying graph; • Solv: this field contains "solve" if the automorphism group of the digraph is solvable and "n-solv" otherwise; • Rad: the radius, that is, half of the length of an alternating cycle; • AtNo: the attachment number, that is, the size of the intersection of two intersecting alternating cycles; • AtTy: the attachment type, that is: "loose" if the attachment number is 1, "antipodal" if 2, and "tight" if equal to the radius, otherwise "—"; • |AltCyc|: the number of alternating cycles; • AltExp: the alter-exponent; • AltPer: the alter-perimeter; • AltSeq: the alter-sequence; • IsGWD: "yes" if the digraph is generalized wreath, and "no" otherwise. 4.7 The data on arc-transitive 4-GHATs The "Census-GHAT-1k-data.csv" file concerns arc-transitive 4-GHATs . Each line of the file represents one of the graphs in the census, and has nine fields, described below. Note, however, that the file does not contain the generalised wreath graphs. 146 Ars Math. Contemp. 8 (2015) 133-148 • Name: the name of the graph (for example GHAT[9,1]); • |v| : the order of the graph; • gir: the girth (length of a shortest cycle) of the graph; • bip: this field contains "b" if the graph is bipartite and "nb" otherwise; • CayTy: this field contains "Circ" if the graph is a circulant (that is, a Cayley graph on a cyclic group), "AbCay" if the graph is Cayley graph on an abelian group, but not a circulant, and "Cay" if it is a Cayley but not on an abelian group - it contains "n-Cay" otherwise; • | Av |: the order of the vertex-stabiliser in the automorphism group of the graph; • |Gv |: a sequence of the orders of vertex-stabilisers of the maximal half-arc-transitive subgroups of the automorphism group - up to conjugacy in the automorphism group; • solv: this field contains "solve" if the automorphism group of the graph is solvable and "n-solv" otherwise; • [|ConCyc|]: the sequence of the lengths of A-consistent oriented cycles of the graph (one cycle per each A-orbit, where A is the automorphism group of the graph) - the symbols "c" and "s" indicate whether the corresponding cycle is chiral or symmetric - for example, [4c; 4c; 10s] means there are two chiral orbits of A-consistent cycles, both containing cycles of length 4, and one orbit of symmetric consistent cycles, containing cycles of length 10. 4.8 The data on 4-HATs The "Census-HAT-1k-data.csv" file concerns 4-HATs. Each line of the file represents one of the graphs in the census, and has 16 fields. The fileds |v|, gir, bip, and Solv are as in Section 4.7, and the fields Rad, AtNo, AtTy, AltExp, AltPer and AltSeq are as in Section 4.6. The remaining fileds as follows: • Name: the name of the graph (for example HAT[27,1]); • IsCay: this field contains "Cay" if the graph is Cayley and "n-Cay" otherwise; • |Gv |: the order of the vertex-stabiliser in the automorphism group of the graph; • CCa: the length of a shortest consistent cycle; • CCb: the length of a longest consistent cycle; • MetaCircCl: "{}" if the graph is not a meta-circulant; otherwise a set of classes of meta-circulants that represents the graph. References [1] B. Alspach, D. Marusic, L. Nowitz, Constructing graphs which are 1 -transitive, J. Austral. Math. Soc. Ser. A 56 (1994), 391-402. [2] B. Alspach, T. D. Parsons, A construction for vertex-transitive graphs Canad. J. Math. 34 (1982), 307-318. [3] N. Biggs, Aspects of symmetry in graphs, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 27-35, Colloq. Math. Soc. Janos Bolyai, 25, North-Holland, Amsterdam-New York, 1981. P. Potočnik et al.: A census of 4-valent half-arc-transitive graphs. 147 [4] M. Boben, S. Miklavic, P. Potočnik, Consistent cycles in 1 -arc-transitive graphs, Electron. J. Combin. 16 (2009), # R5, 1-10. [5] W. Bosma, J. Cannon and C. Playoust, The Magma Algebra System I: The User Language, J. Symbolic Comput. 24 (1997), 235-265. [6] I. Z. Bouwer, Vertex and edge-transitive but not 1-transitive graphs, Canad. Math. Bull. 13 (1970), 231-237. [7] M. D. E. Conder, D. Marusic, A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer, J. Combin. Theory Ser. B 88 (2003) 67-76. [8] M. D. E. Conder, P. Potocnik, P. Sparl, Some recent discoveries about half-arc-transitive graphs, Ars. Math. Contemp. 8 (2005) [9] M. D. E. Conder, All rotary maps on closed surfaces with up to 1000 edges, https:// www.math.auckland.ac.nz/~conder/https://www.math.auckland.ac.nz/^conder/, accessed October 2013. [10] J. H. Conway, Talk given at the Second British Combinatorial Conference at Royal Holloway College, Egham, 1971. [11] D. Firth, An algorithm to find normal subgroups of a finitely presented group up to a given index, PhD Thesis, University of Warwick, 2005. [12] G. Glauberman, Isomorphic subgroups of finite p-subgroups, Canad. J. Math. 23 (1971), 9831022. [13] K. Kutnar, D. Marusic, P. Sparl, R.-J. Wang, M.-Y. Xu, Classification of half-arc-transitive graphs of order 4p, European J. Combin. 34 (2013), 1158-1176. [14] A. Malnic, D. Marusic, N. Seifter, P. Sparl, B. Zgrablic, Reachability relations in digraphs, Europ. J. Combinatorics 29 (2008), 1566-1581. [15] A. Malnic, D. Marusic, Constructing 4-valent 1 -Transitive Graphs with a Nonsolvable Automorphism Group, J. Combin. Theory Ser. B 75 (1999), 46-55. [16] D. Marusic, Recent developments in half-transitive graphs, Discrete Math. 182 (1998), 219231. [17] D. Marussics, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser.B 73 (1998), 41-76. [18] D. Marusic, Quartic half-arc-transitive graphs with large vertex stabilizers, Discrete Math. 299 (2005), 180-193. [19] D. Marussics, R. Nedela, On the point stabilizers of transitive groups with non-self-paired suborbits of length 2, J. Group Theory 4 (2001), 19-43. [20] D. Marussics, P. Potocsnik, Bridging Semisymmetric and Half-Arc-Transitive Actions on Graphs, European J. Combin. 23 (2002), 719-732. [21] D. Marussics, C. E. Praeger, Tetravalent graphs admitting half-transitive group actions: alternating cycles, J. Combin. Theory Ser. B 75 (1999), 188-205. [22] D. Marusic, P. Sparl, On quartic half-arc-transitive metacirculants, J. Algebraic Combin. 28 (2008), 365-395. [23] D. Marusic, A. Orbanic, P. Sparl, A list of 1 -arc-transitive tetravalent graphs with the vertex-stabiliser of order 2, unpublished work, available upon request from P. Sparl, primoz.sparl@pef.uni-lj.si. [24] D. Marusic, M.-Y. Xu, 2-transitive graph of valency 4 with a nonsolvable group of automorphisms, J. Graph Theory 25 (1997), 133-138. 148 Ars Math. Contemp. 8 (2015) 133-148 [25] S. Miklavic, A note on a conjecture on consistent cycles, Ars Math. Contemp. 6 (2013), 389392. [26] S. Miklavic, P. Potocnik, S. Wilson, Overlap in consistent cycles, J. Graph Theory 55 (2007), 55-71. [27] P. Potocnik, P. Spiga, G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J. Symbolic Comput. 50 (2013), 465-477. [28] P. Potocnik, P. Spiga, G. Verret, Census of 2-valent arc-transitive digraphs, http://www. fmf.uni-lj.si/~potocnik/work.htm, accessed October 2013. [29] P. Potocnik, P. Spiga, G. Verret, Census of (2, *)-groups, http://www.fmf.uni-lj.si/ -potocnik/work.htm, accessed October 2013. [30] P. Potocnik, G. Verret, On the vertex-stabiliser in arc-transitive digraphs, J. Combin. Theory Ser. B. 100 (2010), 497-509. [31] P. Potocnik, S. Wilson, Census of tetravalent edge-transitive graphs, https://jan.ucc. nau.edu/~swilson/C4Site/BigTable.html, accessed October 2013. [32] C. E. Praeger, Highly arc transitive digraphs, European J. Combin. 10 (1989), 281-292. [33] M. Sajna, Half-transitivity of some metacirculants, Discrete Math. 185 (1998), 117-136. [34] P. Sparl, A classification of tightly attached half-arc-transitive graphs of valency 4, J. Combin. Theory Ser. B 98 (2008), 1076-1108. [35] P. Sparl, On the classification of quartic half-arc-transitive metacirculants, Discrete Math. 309 (2009), 2271-2283. [36] P. Sparl, Almost all quartic half-arc-transitive weak metacirculants of Class II are of Class IV, Discrete Math. 310 (2010), 1737-1742. [37] P. Spiga, G. Verret, On the order of vertex-stabilisers in vertex-transitive graphs with local group Cp x Cp or Cp i C2,http://arxiv.org/pdf/1311.4308.pdf. [38] W. T. Tutte, Connectivity in Graphs, University of Toronto Press, Toronto (1966).