/^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) 149-162
Some recent discoveries about half-arc-transitive graphs
Dedicated to Dragan Marusic on the occasion of his 60th birthday
Marston D. E. Conder *
Mathematics Department, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand
Primož Potočnik t
Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia and
IAM, University of Primorska, Muzejski trg 2, 6000 Koper, Slovenia
Primož Sparl *
Faculty of Education, University of Ljubljana, Kardeljeva ploscad 16, 1000 Ljubljana, Slovenia and
Institute for Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia and
IAM, University ofPrimorska, Muzejski trg 2, 6000 Koper, Slovenia
Received 11 October 2013, accepted 5 June 2014, published online 22 September 2014
Abstract
We present some new discoveries about graphs that are half-arc-transitive (that is, vertex- and edge-transitive but not arc-transitive). These include the recent discovery of the smallest half-arc-transitive 4-valent graph with vertex-stabiliser of order 4, and the smallest
*The first author was supported by a James Cook Fellowship and a Marsden Fund grant (UOA1015) from the Royal Society of New Zealand
^The second author was supported by the Slovenian Research Agency, projects L1-4292 and P1-0222.
* The third author was supported in part by the Slovenian Research Agency, projects J1-4010 and J1-4021 and program P1-0285.
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
150
Ars Math. Contemp. 8 (2015) 149-162
with vertex-stabiliser of order 8, two new half-arc-transitive 4-valent graphs with dihedral vertex-stabiliser D4 (of order 8), and the first known half-arc-transitive 4-valent graph with vertex-stabiliser that is neither abelian nor dihedral. We also use half-arc-transitive group actions to provide an answer to a recent question of Delorme about 2-arc-transitive digraphs that are not isomorphic to their reverse.
Keywords: Graph, edge-transitive, vertex-transitive, half-arc-transitive. Math. Subj. Class.: 05E18, 20B25
1 Introduction
A graph X is said to be vertex-transitive, edge-transitive, or arc-transitive, if its automorphism group Aut X acts transitively on the set V(X) of all vertices of X, the set E(X) of all edges of X, or the set A(X) of all arcs (ordered pairs of adjacent vertices) of X, respectively. An arc-transitive graph is also called symmetric. The graph X is called half-arc-transitive if it is vertex-transitive and edge-transitive but not arc-transitive.
(A related class of graphs consists of those which are regular and edge-transitive but not vertex-transitive. Any such graph is called semi-symmetric. Semi-symmetric 3-valent graphs will be the topic of another forthcoming paper by the first two authors.)
Every half-arc-transitive graph X is regular, with even valency — indeed Aut X has two orbits on arcs, with half the arcs emanating from any vertex v lying in each orbit. The smallest possible valency of a half-arc-transitive graph is 4, and this is the valency of the smallest half-arc-transitive graph, a graph on 27 vertices constructed independently by Doyle [7] and Holt [10].
Furthermore, examples exists for every even valency greater than 2. This was proved (in answer to a question by Tutte [21]) by Bouwer [2], who constructed a family of examples of valency 2k for all k > 2, with the property that the stabiliser in Aut X of every vertex v induces the symmetric group Sk on the neighbourhood of v, acting with two orbits of length k. (The latter property was not explicitly mentioned by Bouwer, but may be easily deduced from his construction.)
For valency greater than 4, the vertex-stabilisers in Bouwer's examples are non-abelian. In contrast, for quite some time all known examples of 4-valent half-arc-transitive graphs had vertex-stabilisers that are abelian, or more precisely, elementary abelian 2-groups.
The first known example of a 4-valent half-arc-transitive graph with non-abelian vertex-stabiliser was found in 1999 by Conder and Marusic, who produced an example of order 10752 from a transitive permutation group of degree 32 and order 86016, with dihedral point stabiliser (of order 8) having a non-self-paired sub-orbit; see [4]. Until recently, however, this was the only known example, and no examples were known of 4-valent half-arc-transitive graphs with vertex-stabiliser that is neither abelian nor dihedral.
In this paper, we exhibit a number of new examples with particular properties.
In Section 3 we give the smallest half-arc-transitive 4-valent graph (on 256 vertices) with vertex-stabiliser of order 4, and also the two smallest half-arc-transitive 4-valent graphs (on 768 vertices) with vertex-stabiliser of order 8. The fact that the former has
E-mail addresses: m.conder@auckland.ac.nz (Marston D. E. Conder), primoz.potocnik@fmf.uni-lj.si (Primož Potočnik), primoz.sparl@pef.uni-lj.si (Primož Sparl)
Marston D. E. Conder et al.: Some recent discoveries about half-arc-transitive graphs
151
order 256 disproves the conjecture by Feng, Kwak, Xu and Zhou [8] that every 4-valent half-arc-transitive graph of prime-power order has vertex stabilisers of order 2. Then in Section 4 we describe two new half-arc-transitive 4-valent graphs with vertex-stabiliser D4 (of order 8), and in Section 5 we produce the first known half-arc-transitive 4-valent graph with vertex-stabiliser that is neither abelian nor dihedral. (In this last example, the vertex-stabiliser is isomorphic to D4 x C2, of order 16.)
In Section 6 we use half-arc-transitive group actions to provide an answer to a recent question of Charles Delorme [5] about 2-arc-transitive digraphs that are not isomorphic to their reverse. The reverse Rev(D) of a digraph D is obtained by reversing all the arcs of D, and then D is called self-reverse if Rev(D) is isomorphic to D. Also a 2-arc in a digraph D is a directed walk (v0, vi, v2) of length 2 on three vertices, and then D is called arc-transitive or 2-arc-transitive if its automorphism group Aut D is transitive on the set of all arcs in D or the set of all 2-arcs in D, respectively. In [5, §5.2], Delorme asked this question: Do finite digraphs exist that are vertex-transitive, arc-transitive and 2-arc-transitive, but not self-reverse? We answer this question in the affirmative. Finally, we make some concluding remarks and pose some further questions in Section 7.
2 Further background
Before proceeding, we provide some more background information. Throughout this paper, graphs are assumed to be finite and simple, and unless otherwise specified, also undirected and connected.
For any graph (or digraph) X, we let V(X), E(X) and A(X) be the vertex-set, edge-set, and arc-set of X, respectively, and we let Aut X be the automorphism group of X. As mentioned earlier, we say that X is vertex-transitive, edge-transitive, or arc-transitive, if AutX is transitive on V(X), E(X) or A(X), respectively, and we say that the graph X is half-arc-transitive if it is vertex- and edge-transitive but not arc-transitive.
More generally, if G is any group of automorphisms of X (that is, any subgroup of Aut X), then G is said to be vertex-transitive, edge-transitive or arc-transitive on X if G acts transitively on V(X), E(X) or A(X), respectively, and G is half-arc-transitive on X if G is vertex- and edge-transitive but not arc-transitive on X. In the latter case, we also say that X is (G, 1 )-arc-transitive, or (G, 1, H)-arc-transitive when it needs to be stressed that the stabiliser Gv of a given vertex v is isomorphic to a particular subgroup H of G.
Next, we repeat an explanation given in [14] of a connection between half-arc-transitive group actions and transitive permutation groups with a non-self-paired sub-orbit.
Let G be a transitive permutation group acting on a set V. An orbital of G is an orbit of the natural action of G on the Cartesian product V x V, and a sub-orbit of G on V is an orbit of the stabiliser Gv of a given point v G V. For any given point v G V there is a 1-to-1 correspondence between the set of all orbitals of G and the set of all sub-orbits of G on V (with regard to v), with the orbital containing the pair (v, w) G V x V corresponding to the orbit of Gv containing w. In particular, the diagonal orbital {(w, w) : w G V} corresponds to the trivial sub-orbit {v}.
For any sub-orbit W of G (with regard to v), let AW be the corresponding orbital of G, which contains the pair (v, w) for each w G W. Then the orbital digraph X(G, V; W) of (G, V) relative to W is the digraph (or oriented graph) with vertex-set V and arc-set AW. The underlying undirected graph, with orientations of all arcs ignored, is denoted by X* (G, V; W).
152
Ars Math. Contemp. 8 (2015) 149-162
The paired orbital of a given orbital A is the orbital A' = {(v, w) : (w, v) G A}. The orbital A is said to be self-paired if A' = A, and non-self-paired otherwise; in the latter case A n A' = 0. This notion of pairing also carries over to sub-orbits in a natural way. It is important to note that for a non-self-paired sub-orbit W of G, the orbital digraph X(G, V; W) is an oriented graph, while the underlying undirected graph X*(G, V; W) admits a half-arc-transitive action of G.
In the special case where V is the set (G: H) of all (right) cosets of a subgroup H of G, and W is a non-self-paired sub-orbit of the action of G on V (by right multiplication), the graph X*(G, V; W) is (G, 2, H)-arc-transitive, with valency 2|W|. This graph might or might not be half-arc-transitive, depending on whether it admits any additional automorphisms that reverse an arc. The example in [4] began with H being dihedral of order 8, and had G as its full automorphism group.
For some further references on half-arc-transitive graphs (which are often referred to simply as half-transitive graphs), see the survey paper by Marusic [15], and for the theory of permutation groups, see [6, 22].
3 The smallest half-arc-transitive 4-valent graphs with vertex-stabilisers of order 4 and 8
In this section we present the smallest 4-valent half-arc-transitive graphs for which the vertex-stabilisers have order 4 and 8, respectively. These graphs have 256 and 768 vertices, and will also appear in a recently computed census of all 4-valent half-arc-transitive graphs of order at most 1000 (see [18]).
3.1 Stabiliser of order 4
If G is the automorphism group of a half-arc-transitive 4-valent graph such that the stabiliser H in G of a vertex v has order 4, then H is isomorphic to the Klein group V4, and so is generated by two commuting involutions p and q. At the same time, G is generated by H and an automorphism a mapping v to an out-neigbour w of v (in one of the two corresponding orbital digraphs). Generators p and q of H can be chosen in such a way that q = a-1pa. In addition, since H is the stabiliser in a transitive permutation group G, the core of H in G is trivial.
Conversely, given a group G generated by two commuting involutions p and q, and an element a such that q = a-1 pa, where p and q generate a core-free subgroup H of G, one can construct the orbital digraph X = X* (G, V; W), where V is the coset-space (G: H), with G acting upon V by right-multiplication, and W is the sub-orbit of this action containing the coset Ha. It can be seen that such a sub-orbit is necessarily non-self-paired, implying that X is 4-valent and admits G as a half-arc-transitive group of automorphisms. In particular, if X admits no additional automorphisms, then X is a half-arc-transitive graph with valency 4 and vertex-stabiliser V4. This happens quite frequently, although not for small orders.
Candidates for G of order up to 1023 can be checked quite easily using the small groups database in Magma [1], but none of them has the required properties. Order 1024 is more challenging by this approach, since there are 49 487 365 422 groups of order 1024, and they are not easily available.
Instead, we can use an algorithm for finding all normal subgroups of given index in a finitely-presented group, as described in [3], or better still, [9]. The latter version is
Marston D. E. Conder et al.: Some recent discoveries about half-arc-transitive graphs
153
implemented in Magma [1] as the LowIndexNormalSubgroups procedure. We can apply this to the finitely-presented group F = (p,q,a | p2 = q2 = (pq)2 = a-1paq =1), and for every normal subgroup N found, consider the quotient F/N as a candidate for G.
It turns out there are 3102 normal subgroups of index up to 1024 in F, and remarkably, four of them give good candidates. The quotient via one such normal subgroup is the group G used in the following:
Theorem 3.1. Let G be the group with presentation
(p,q,a |p2 = q2 = (pq)2 = a-1paq = a8 = (pa-2qa2)2 = a3qapa-1pqa-2qa-1 q =1),
and let W be the sub-orbit with regard to H = (p, q) containing the coset Ha. Then G has order 1024, and X *(G, H; W) is a 4-valent half-arc-transitive graph of order 256, girth 8 and diameter 8, with automorphism group G, and vertex-stabiliser Gv isomorphic to V4.
Indeed the sub-orbit W containing the coset Ha is {Ha, Hap}, of size 2, and is not self-paired, its paired sub-orbit being {Ha-1, Ha-1q}. The graph X = X*(G, H; W) can easily be constructed with the help of Magma, and the fact that Aut X = G verified using the function AutomorphismGroup.
As mentioned in the first section, the fact that the order of this graph is 256 = 28 shows that the conjecture by Feng, Kwak, Xu and Zhou [8] (that every 4-valent half-arc-transitive graph of prime-power order has vertex stabilisers of order 2) is false.
By inspecting normal subgroups of G = Aut X, one finds that G has an elementary abelian normal subgroup K of order 16, and another normal subgroup J isomorphic to C4 x C4 x C2. With respect to these two normal subgroups, X is an abelian regular cover of two smaller graphs, namely the Rose-window graph RW8(6, 5), as defined in [23, §5], and the "doubled" 8-cycle DC8 (that is, the (multi)graph obtained from the directed cycle C8 by doubling each edge). Accordingly, the graph X has at least two alternative constructions as a covering graph.
Theorem 3.2. The graph X = X*(G, H; W) in Theorem 3.1 is an abelian regular cover of the Rose-window graph RW8(6, 5), with covering group K = C24, and also an abelian regular cover of the doubled cycle DC8, with covering group J = C4 x C4 x C2.
In fact, the Rose-Window graph RW8(6,5) is isomorphic to the Cartesian product C4 □ C4 of two cycles of length 4, and moreover, the quotient projection X ^ X/K is a covering projection, and G/K is the largest subgroup of Aut (X/K) acting half-arc-transitively on X/K. (For background information on quotients and covering projections of graphs, see [12, 20] for example.)
The construction of X as an abelian regular cover of DC8 can be described as follows.
Let
J = (a,b, c | a4 = b4 = c2 = [a, b] = [a, c] = [b, c] = 1),
which is abelian of order 32, and isomorphic to C4xC4 xC2, and let ip be the automorphism of J of order 8 that takes a to b, and b to ac, and c to a2c, or equivalently, is given by
p(aibjck) = aj+2kbicJ+k for 0 < i,j < 3 and 0 < k < 1.
Now label the vertices of DC8 with the elements of Z8 in a natural way, and label the edges with the elements of {ei : i e Z8} U {fi : i e Z8} in such a way that the two edges incident to both i and i + 1 are labelled ei and fi, for each i e Z8. We can now describe
154
Ars Math. Contemp. 8 (2015) 149-162
a certain voltage assignment of the voltages from J to the set of the arcs of DC8. (For the terminology on graph coverings via voltage assignments, see [13].) For each i e Z8, we put the trivial voltage 1 on all of the arcs corresponding to the edge fj, and put the voltage on the arc corresponding to ej (directed from i to i + 1). It can easily be verified that the covering graph obtained in this way is a 4-valent half-arc-transitive graph of order 256, with vertex stabilisers of order 4, as above.
Similarly, the other three normal subgroups giving good candidates for G all give rise to half-arc-transitive graphs that are isomorphic to X.
Let us mention also that 4-valent half-arc-transitive graphs with vertex stabilisers of order 4 have been known to exist for some time. In fact, an infinite family of such graphs was constructed in each of the papers [11] and [16]. These graphs, however, are very large. The smallest graph in the first family has order > 8 • 1013, and the smallest one in the second family has order 9 979 200.
3.2 Stabiliser of order 8
As was shown in [17] (see also [19]), if the vertex-stabiliser H = Gv in a half-arc-transitive group of automorphisms G of a connected tetravalent graph X has order 8, then H is either elementary abelian or dihedral. Moreover, as in the case where |H | = 4, the group G is generated by H and any element a of G that maps the vertex v to an out-neighbour of v. Using these observations we can prove the following:
Theorem 3.3. Let X be a 4-valent half-arc-transitive graph with automorphism group G, and suppose the stabiliser H = Gv of a vertex v has order 8.
(a)	If H is dihedral, then G is a quotient of the finitely generated group
63,1 = {p, q,r,a | p2 = q2 = r2 = [p, q] = [q, r] = 1, [p, r] = q,q = a-1pa, r = a-1qa) of order 8|V (X )|. There is no such graph X of order up to 768.
(b)	If H is abelian, then G is a quotient of the finitely generated group
63,0 = {p, q,r,a | p2 = q2 = r2 = [p, q] = [p, r] = [q, r] = 1, q = a-1 pa, r = a-1qa)
of order 8|V (X )|. There is no such graph of order less than 768, but there are two (non-isomorphic) examples of order 768, say X1 and X2, which arise from orbital digraphs for quotients of 63,0 with respect to the additional relator sets
R1 = {a12, (ra2pa-2)2, a-1pa-4rqpa6pqa-1, a-1rapa-2pa-1rpapa2papa-1} and	R2 = {a12, (ra2pa-2)2,rapa-1ra2qpa-4ra2},	respectively.
Proof.
(a)	If H is dihedral, then the generators p, q, r of H = Gv can be chosen so that they satisfy the relations p2 = q2 = r2 = [p, q] = [q, r] = 1 and [p, r] = (pr)2 = q, and the automorphism a (moving v to an out-neighbour of v) chosen so that q = a-1pa and r = a-1qa. Thus G is a quotient of 63,1, of order 8|V(X)|. Inspection of the normal subgroups of index at most 8 • 768 = 6144 in 63,1, and the corresponding orbital digraphs, shows there are no such X of order up to 768 (with H = Gv dihedral of order 8).
(b)	If H is abelian, then G is a quotient of 63,0, by a similar argument to that in part (a). Computation of normal subgroups of index at most 6144 in G3<0 shows there is no such X of order less than 768 (with H = Gv abelian of order 8), but there are two (non-isomorphic)
Marston D. E. Conder et al.: Some recent discoveries about half-arc-transitive graphs
155
examples which arise from normal subgroups of index 768, namely the normal closures of the sets and R2 as given. In each case, it is easy to check using Magma that the corresponding quotient of G3j0 is the full automorphism group of the graph.	□
Theorem 3.4. The graphs X1 and X2 in Theorem 3.3 are non-isomorphic regular covers of the doubled cycle DC3, as well as elementary abelian regular covers of the so-called Hill Capping HC (Q3) of the cube Q3 (see [24]).
Proof. The automorphism group of Xi has a normal subgroup Ki of index 24 and order 256, generated by
x = apa-ir, y = a3qra3rq = a6[a3, rq], z = a3pqra3rqp = a6[a3, rqp] and u = a3,
all of which have order 4, with x, y and z generating an abelian normal subgroup of order 64, and xu = xy2z2, yu = x2y-iz2 and zu = z-i. The centre and derived subgroup of Ki are the elementary abelian 2-subgroups {x2,y2, z2,u2} and {x2,y2, z2), of orders 16 and 8 respectively. (In particular, Ki has nilpotency class 2.)
This subgroup Ki acts semi-regularly on V(Xi), and the quotient graph Xi/Ki is isomorphic to the doubled cycle DC3. It follows that Xi can be reconstructed as a regular cover of DC3, with covering group Ki. This can be achieved as follows. First, label the vertices of DC3 with the elements of Z3, and label the edges of DC3 with elements of the set {ei : i e Z3} U {fi : i e Z3}, so that ei and fi are the two edges incident to both i and i + 1 (for each i e Z3). Also let ei and fi be the corresponding arcs from i to i +1, for i e Z3. Then the graph Xi is isomorphic to the cover of DC3 obtained from the voltage assignment p on DC3 defined by
p(eo) = p(e2) = 1, p(ei) = u, p(fo) = x, p(fi) = uxy and p(f2) = (yz)-i.
Similarly, the automorphism group of X2 has a normal subgroup K2 of index 24 and order 256, and nilpotency class 2, acting semi-regularly on V(X2). The quotient graph X2/K2 is again isomorphic to the doubled cycle DC3, and hence X2 can be reconstructed as a regular cover of DC3, with covering group K2 (not isomorphic to Ki).
Finally, each of Aut Xi and Aut X2 contains an elementary abelian normal subgroup K of order 16, with respect to which the quotient graphs Xi/K and X2/K are both isomorphic to HC (Q3). Hence Xi and X2 can be reconstructed as elementary abelian covers
of HC(Q3).	□
Here we note that the graph HC(Q3) happens to be the unique tetravalent arc-transitive graph of order 48, girth 4, and diameter 6.
4 Two new half-arc-transitive graphs with vertex-stabiliser D4
The first (and until recently, the only) known example of a half-arc-transitive 4-valent graph with non-abelian vertex-stabiliser is described in [4].
This graph has 10752 vertices, and its automorphism group G of order 86 016 is generated by two elements a and b of orders 8 and 24, which satisfy the (defining) relations
a8 = (ab-i)2 = a-2bab-2ab = (ab3ab2ab2)2 = a-3ba2b-3a2b = (a2ba2babab)2 = a3b2a2b2aba3bababab2 = 1. The graph is the underlying graph of the orbital digraph X (G, V; W) where V is the coset
156
Ars Math. Contemp. 8 (2015) 149-162
space (G: H) for the subgroup H generated by p = a-1b and q = a-1pa and r = a-1qa, and W is the non-self-paired sub-orbit {Ha, Hb}.
In response to a comment made by Dragan Marusic about this graph being somewhat unique, in a lecture at a workshop at the Fields Institute in October 2011, the first author decided to look for more examples. Somewhat surprisingly, it turns out there is another example on 10752 vertices (with vertex-stabiliser D4), not isomorphic to the first. Also there exists an example on 21 870 vertices, with similar properties.
Theorem 4.1. There are at least two non-isomorphic half-arc-transitive 4-valent graphs of order 10 752 with non-abelian vertex-stabiliser of order 8.
The automorphism group of the new one of order 10 752 is a different group G of order 86 016, generated by two elements a and b of orders 16 and 12 which satisfy the (defining) relations
a16 = b12 = (ab-1)2 = a-2bab-2ab = (ab3ab2ab2)2 = a-3b2ab-3ab2 = (a2b2abab2ab)2 = a5b3a5bab = 1.
Again if V is the coset space (G : H) for the subgroup H generated by p = a-1b and q = a-1pa and r = a-1qa, and W is the non-self-paired sub-orbit {Ha, Hb}, then the 4-valent underlying graph of the orbital digraph X (G, V; W) is half-arc-transitive, but it is not isomorphic to the first example.
Theorem 4.2. There exists at least one half-arc-transitive 4-valent graph of order 21 870 with non-abelian vertex-stabiliser of order 8.
The automorphism group of the one we found has order 174 960, and is generated by two elements a and b of orders 8 and 24 which satisfy the (defining) relations
a8 = (ab-1)2 = a-2bab-2ab = a-3ba2b-3 a2b = (a3b)5 = a3b-1a-3b2ababab2ab2a2b = 1.
Both of these new examples were found with the help of Magma [1], in the same way as the first one in [4]. Also MAGMA can be used to verify that the full automorphism group of the graph is as stated, in each case.
5 A half-arc-transitive 4-valent graph with a non-abelian and non-dihedral vertex-stabiliser
In his 2011 lecture at the Fields Institute (mentioned in the previous section), Dragan Marusic made the observation that no half-arc-transitive 4-valent graph was known with vertex-stabiliser that is neither abelian nor dihedral. We provide an example here.
We begin with an arc-transitive 4-valent graph on 90 vertices, which can be constructed from a group G of order 1440, generated by two elements c and d subject to the relations
c8 = d10 = (cd)6 = (cd-1)2 = (cd2)4 = c-2dcd-2cd = c3d-1 c-2dcdc-2d-1 = d2 c-3d-1c4d-1c-3 d2 = 1.
Let H be the subgroup generated by p = c-1d and conjugates q = c-1pc, r = c-1qc and s = c-1rc. Then H is isomorphic to the direct product D4 x C2, or order 16. If V
Marston D. E. Conder et al.: Some recent discoveries about half-arc-transitive graphs
157
is the coset space (G : H), and W is the non-self-paired sub-orbit {Hc, Hd}, then the 4-valent underlying graph X of the orbital digraph X (G, V, W) is arc-transitive, but admits a half-arc-transitive action of G. (In fact, its full automorphism group has order 2880.)
The half-arc-transitive action of G on X lifts to the action of a larger group G on a regular cover of X, which we will prove is half-arc-transitive.
The group we take is the transitive permutation group G of degree 60, generated by the elements
a = (1, 2)(3, 4, 6, 8,12,17, 21, 27, 36,44, 53, 60, 59, 52, 47, 37, 45, 35, 26, 20,16,11, 7, 5) (9,13,18, 23, 30, 40, 51, 48, 57, 58, 50, 39, 29, 22, 28, 38, 34, 25, 33, 24,19,15,10,14) (31, 41, 49, 42)(32, 43)(46, 55, 54, 56)
and
b = (1, 2, 5, 3,14, 6, 8, 29,17,47, 55,46, 37, 36,48, 53, 60, 30, 52, 21, 56, 54, 27, 45, 38, 26, 20,19,11, 7)(4, 9,13,42, 31, 50, 39,12, 22, 51, 44, 57, 58, 41, 49,18, 23, 59,40, 28, 35, 34, 25, 43, 32, 33, 24,16,15,10).
This group G is imprimitive, with blocks of sizes 3, 6 and 30. The action of G on the blocks of size 3 (which are {1,55,56} and its images) gives an epimorphism from G to the group G above, with elementary abelian kernel K of order 310.
Let p = a-1b, q = a-1pa, r = a-1qa and s = a-1ra. These elements satisfy the relations p2 = q2 = r2 = s2 = b-1pbq = b-1qbr = b-1pqrbs = (rs)2 = (qs)2 = 1, as well as pa-1b = a-1paq = a-1qar = a-1ras = 1 and others. The subgroup H generated by p, q, r and s has order 16, and just like H above, is isomorphic to D4 x C2.
Theorem 5.1. With the notation above, let X be the underlying graph of the orbital digraph X(G, V; W), where V is the coset space (G: H) and W is the sub-orbit {Ha, Hb}. Then X is a 4-valent half-arc-transitive graph of order 90 • 310, with automorphism group G, and vertex-stabiliser H = Gv = D4 x C2. In fact, X is a regular cover of X, and the action of G on X projects to the action of G on X.
Proof. The sub-orbit W = {Ha, Hb} is non-self-paired, and so X is 4-valent, and G acts half-arc-transitively on X, with vertex-stabiliser H = D4 x C2. The group G has order 1440 • 310, and so the order of X is as given. This order makes X too large to construct and analyse easily using Magma, but nevertheless we can study the permutation representation of G on the right coset space V closely enough to prove that G is the full automorphism group of X. We will not provide all details, but we explain most of the argument below.
First, let '1' be the vertex H in X, and let x1, x2, x3 and x4 be the four neighbours of 1 (which are the cosets Ha, Hb, Ha-1 (= Hb-1) and Ha-1s). Then by vertex-transitivity, the edges of X are images of the edges {1, xj under the action of elements of G.
We can use that fact to find all vertices within a given small distance from vertex 1. The numbers of vertices at distances 0 to 9 from vertex 1 are 1, 4, 12, 36, 108, 324, 972, 2 916, 8 748 and 26 050, respectively. It turns out that no two vertices at distance 8 from vertex 1 are adjacent, and that no three such vertices have a common neighbor at distance 9 from vertex 1. It follows that the girth of X is 18, and that there are 3 • 8748 - 26050 = 194 girth cycles (of length 18) in X containing the vertex 1.
Moreover, we find easily that a given 1-arc with initial vertex 1 lies in 97 girth cycles, a given 2-arc with initial vertex 1 lies in 31 or 35 girth cycles, a given 3-arc with initial vertex 1 lies in 10, 11 or 13 girth cycles, a given 4-arc with initial vertex 1 lies in 3, 4 or 7
158
Ars Math. Contemp. 8 (2015) 149-162
girth cycles, and a given 5-arc with initial vertex 1 lies in 1, 2, 3 or 5 girth cycles. In fact, just one of the 2-arcs extending a given 1-arc (1, xj) lies in 35 girth cycles, with the other two lying in 31 .
Now if a 2-arc of the form (u, v, w) lies in exactly 35 girth cycles, let us call the vertex w the 'twin' of vertex u at vertex v. This gives a 'twinning' (or pairing) of neighbours at each vertex in the usual way, but an important point is that this is a property of X (rather than just the action of G). Also it shows that the stabiliser in Aut X of any vertex of X is a 2-group.
Label the neighbours of vertex 1 so that {xi, x3} and {x2, x4} are pairs of twins, and for each xj, let yj be the twin of vertex 1 at xj, and let zj and wj be the other two (twin) neighbours of xj.
Also let us call a 5-arc 'special' if it lies in a unique girth cycle. If a 5-arc (u, xj, 1, xj, v) with middle vertex 1 is special, then the analysis shows that {xj, xj } is not a twin pair. Note that Aut X must permute the special 5-arcs among themselves.
Next, let B be the ball of radius 2 centred at vertex 1, and consider the pointwise stabiliser of B in AutX. If the automorphism h fixes every vertex in B, then for every 2-arc of the form (1, xj, v), we see that h fixes the twin of xj at vertex w, and for every special 5-arc (u, xj, 1, xj, v) with middle vertex 1, also h fixes every vertex in the unique girth cycle that contains it. These two observations are enough to show that h fixes every vertex at distance 3 from vertex 1. Then by induction and connectedness, the automorphism h is trivial. Hence every automorphism of X is completely determined by its effect on B.
Now consider the permutations induced by each of p, q, r, s and a on B. We can choose the labels xj, yj, zj and wj of the 16 vertices of B \ {1} such that
•	p induces (x1, x3)(y1, y3)(z1, z3)(w1, w3)(z4, w4), and fixes all other vertices of B,
•	q induces (z1, w1)(z3, w3), and fixes all other vertices of B,
•	r induces (z2, w2)(z4, w4), and and fixes all other vertices of B,
•	s induces (x2, x4)(y2, y4)(z2, z4)(w2, w4)(z3, w3), and fixes all other vertices of B, and similarly,
•	a induces a permutation of the form (1, x1, z1,..., z2, x2)(x3, w2,..., y2)(x4, y1,..., w2)
fe ...x^ ...X^ ...x^ ...x^ ...x^...)....
Next, suppose there is some automorphism g of X that fixes vertex 1 and all its neighbours xj, and the twins yj of vertex 1 at those neighbours, but does not lie in the subgroup generated by q and r. Note that this automorphism g would have to fix or swap each pair {zj, wj}. Multiplying by q or r or qr if necessary, we can suppose that g fixes also the vertices z1, w1, z2 and w2, and so g induces either (z3, w3) or (z4, w4) or (z3, w3)(z4, w4) on the 2-ball B.
Then in particular, by considering the permutations induced by various elements on the 2-ball B, and the fact that the point wise stabiliser of B is trivial, we deduce that g centralises q and r, and conjugates p to either p or pq, and conjugates s to s or sr. Similarly, g conjugates a to something of the form ah, where h fixes every vertex in B with the possible exception of z3, w3, z4 and w4, and in particular, it follows that h commutes with each of q and r, and h conjugates p to p or pq, and conjugates s to s or sr, as well. But q = p°, and so if g conjugates p to pq, we find that q = qg = (p°)g = (pg)°s = (pq)ah = (qr)h = qr, which forces r to be trivial, contradiction. Thus pg = p. Since p induces (x1, x3)(y1, y3)(z1, z3)(w1, w3)(z4, w4), it follows that g fixes z3 and w3, and
Marston D. E. Conder et al.: Some recent discoveries about half-arc-transitive graphs
159
hence g induces (z4, w4) on B.
Thus every automorphism of X that fixes all the vertices of the 2-ball B apart from (possibly) z3, w3, z4 and w4, must fix z3 and w3, and so equals the identity or g. In particular, h =1 or g, and so g conjugates a to either a or ag. But also we know that g centralizes each of p, q and r, and conjugates s to sr, and hence sr = sg = (ra)g = (rg)°s = rah = sh. Thus h conjugates s to sr as well, and so h cannot be trivial, so h = g. In particular, g conjugates a to ag. But that means g-1ag = ag, which forces g-1 to be trivial, contradiction.
Hence no such g exists.
Next, for the moment, suppose that X is half-arc-transitive, but G is not the full automorphism group of X. Then there must be some automorphism g of X fixing the vertex 1 and its neighbours x» (and their twins y»), but not lying in G. By what we just showed above, however, this is impossible. Hence if G = Aut X, then X must be arc-transitive, and Aut X contains G as a subgroup of index 2. In particular, G is normal in Aut X.
Finally, suppose X is arc-transitive, and let t be any automorphism of X taking the arc (1, x1) to the arc (1, x2). Then by the 'twinning' property of X, we know that t must also take x3 to x4, and so t induces either (x 1, x2, x3, x4) or (x 1, x2 )(x3, x4) on the neighbours of 1. Multiplying by p if necessary, we may assume that t induces the double transposition (x1, x2)(x3, x4) on the neighbours of 1, and hence also that t induces (y1, y2)(y3, y4) on their 'twins'. Then since t swaps x1 with x2 and swaps y1 with y2, it must swap the set {z1,w1} of the other two neighbours of vertex x1 with the set {z2,w2} of the other two neighbours of vertex x2, and it follows that t induces either (z1, z2)(w1, w2) or (z1, z2, w1, w2) or (z1, w2, w1, z2) on those four vertices. Similarly, t induces either (Z3, Z4)(w3, W4) or (Z3, Z4, W3, W4) or (23, W4, W3, Z4) on {23, W3, 24, W4}.
This gives 16 possibilities for the effect of t on the 2-ball B, but since we can multiply t by q or r or qr (all of which fix the vertices 1, x» and y for all i), we may reduce the possibilities for t to these four:
t1 = (x1,x2)(x3,x4 )(y1,y2)(y3,y4)(z1,22)(z3,z4)(w1,w2 )(W3,W4), t2 = (x1,x2)(x3,x4)(y1,y2)(y3,y4)(z1,22,W1,W2)(z3, Z4)(W3,W4),
t3 = (x1, x2)(x3, x4)(y1, y2)(y3, y4)(z1, 22)(z3, W4)(w1, W2)(W3, Z4), t4 = (x1, x2)(x3, x4)(y1, y2)(y3, y4)(z1, Z2, W1, W2)(z3, W4)(W3, Z4). In each case, it is easy to check that the candidate for t conjugates the permutation induced by q on the 2-ball to the permutation induced by r, and vice versa. Hence t-1qt = r, and t-1rt = q. Similarly, we find that t-1pt = s and t-1st = p when t = t1, while t-1pt = s and t-1st = pq when t = t2, and t-1pt = rs and t-1st = pq when t = t3, and t-1pt = rs and t-1st = p when t = t4.
Now if t = t1, we find that atat-1 fixes all the vertices 1, xj and y», and so by our earlier observations, atat-1 lies in the subgroup generated by q and r. Since also atat-1 fixes z2 and w2, we deduce that atat-1 = 1 or q, so tat-1 = a-1 or a-1q. Rearranging these (and using the fact that t-1 qt = r), we find that also t-1at = a-1 or a-1q. But a Magma computation shows there is no automorphism of the group G taking a to a-1, and p to s (and q to r, etc.), and also there is no automorphism of G taking a to a-1q, and p to s (and q to r, etc.). Hence t = t1.
Similarly, if t = t2, we find that t-1at = sa-1 or sra-1, which upon rearrangement gives t-1 at = a-1r or a-1rq, but another MAGMA computation shows there is no automorphism of G taking a to a-1r or a-1rq, andp to s (and q to r, etc.). Hence t = t2.
If t = t3, then t-1at = a-1 or a-1q, as in the case of t1. But if t conjugates a to a-1,
160
Ars Math. Contemp. 8 (2015) 149-162
and conjugates p to rs (as t3 does), then t conjugates q = pa to (rs)a 1 = arsa-1 = qr, rather than r, contradiction. Similarly, if t conjugates a to a-1q, and conjugates p to rs (as t3 does), then t conjugates q to rq, again a contradiction. Hence t = t3.
Similarly, if t = t4, then t-1at = a-1r or a-1rq, but both of these possibilities give contradictions when combined with the facts that t conjugates p and q to rs and r, so t = t4. Thus no such t exists, and so X is half-arc-transitive, as claimed.	□
6 Answer to a question of Delorme
We begin this section with the following:
Proposition 6.1. Let X be a half-arc-transitive graph of valence 2k, and let G = Aut X. Then if A is one of the two orbits of G on the arcs of X, then the digraph D with vertex-set V(X) and arc-set A is regular, and admits G as a group of automorphisms, but D is not isomorphic to its reverse.
Proof. First, D has out-valence k and in-valence k, and obviously G acts on D as a group of automorphisms. If D were isomorphic to its reverse digraph Rev(D), then the isomorphism from D to Rev(D) would be an automorphism of X not contained in G, which is a contradiction. Hence D is not self-reverse.	□
Next, recall that an s-arc in a digraph D is a sequence (v0, v1,..., vs) of s + 1 vertices such that any two consecutive vertices vi-1 and v form an arc (vi-1, v).) We note that if k (the in- and out-valence of D) is 2, and s is the largest positive integer such that G acts transitively on the s-arcs of D, then it is well known that |Gv | = 2s (see for example [19]). As a consequence of these things, we have an answer to Delorme's question in [5]:
Theorem 6.2. Let X be the unique half-arc-transitive 4-valent graph of order 256, with automorphism group G of order 1024 and vertex-stabiliser Gv = V4. Then the corresponding digraph D is vertex-transitive, arc-transitive and 2-arc-transitive, but is not self-reverse. Moreover, this is the smallest 4-valent digraph with these properties.
The example provided by Theorem 6.2 is the smallest such digraph that comes from a half-arc-transitive 4-valent graph with vertex-stabiliser of order 4, but in principle, a 2-arc-transitive non-self-reverse digraph could also come from an arc-transitive 4-valent graph X that admits a half-arc-transitive group action. (Indeed there is an arc-transitive 4-valent graph Y on 21 vertices with vertex-stabiliser D4 such that Aut Y contains a half arc-transitive subgroup G with Gv = Z2, such that the corresponding orbital digraph D = X(G, V; W) is not self-reverse; but this example is not 2-arc-transitive.) An inspection of the database of all such graphs of small order [18], however, shows that there is no such graph with fewer than 256 vertices, and so the above example of order 256 is the smallest.
On the other hand, there are infinitely many such examples, since there are infinitely many half-arc-transitive 4-valent graphs with vertex-stabiliser V4; see [11, 16].
In fact, there is an infinite family of half-arc-transitive covers of the smallest example given above. With the help of the Reidemeister-Schreier process (implemented as the Rewrite command in Magma [1]), it can be shown that the kernel of the epimorphism from the group (p, q, a | p2 = q2 = (pq)2 = a-1paq = a8 = (pa-2qa2)2 = 1} to the group of order 1024 above has abelianisation Z23 © Z10. It follows that for every odd positive integer m, there is a half-arc-transitive regular cover of order 256m10, with abelian covering group K = Z^0.
Marston D. E. Conder et al.: Some recent discoveries about half-arc-transitive graphs
161
7 Final remarks
In this paper, we have described the smallest 4-valent half-arc-transitive graphs with vertex-stabilisers of order 4 and 8, respectively. In each case, the vertex-stabiliser is abelian.
It is also known that for any positive integer s, there is at least one 4-valent half-arc-transitive graph with abelian vertex-stabilisers of order 2s; see [16]. The graphs constructed in [16], however, have very large orders. Hence the following question arises naturally.
Question 7.1. What is the order of a smallest 4-valent half-arc-transitive graph with abelian vertex-stabiliser of order 2s, for each s > 4?
Next, we have also found anew 4-valent half-arc-transitive graph with vertex-stabilisers isomorphic to the dihedral group D4, having the same order as the smallest known such graph (on 10 752 vertices). It is not yet known, however, if these two graphs are the smallest such examples. Hence we pose the following question.
Question 7.2. Is there a 4-valent half-arc-transitive graph of order less than 10 752, with non-abelian vertex-stabilisers of order 8?
We have also constructed the first known example of a 4-valent half-arc-transitive graph with vertex-stabilisers that are non-abelian and non-dihedral. This has order 5 314 410, with vertex-stabilisers of order 16. We conclude the paper with the following two questions.
Question 7.3. Is there a 4-valent half-arc-transitive graph of order less than 5 314410, with non-abelian, non-dihedral vertex-stabilisers?
Question 7.4. Does there exist a 4-valent half-arc-transitive graph with non-abelian vertex-stabilisers of order 2s, for every s > 3?
References
[1]	W. Bosma, J. Cannon and C. Playoust, The Magma Algebra System I: The User Language, J. Symbolic Comput. 24 (1997), 235-265.
[2]	I. Z. Bouwer, Vertex and edge transitive, but not 1-transitive, graphs. Canad. Math. Bull. 13 (1970), 231-237.
[3]	M. Conder and P. Dobcsanyi, Applications and adaptations of the low index subgroups procedure, Math. Comp. 74 (2005), 485-497.
[4]	M. D. E. Conder and D. Marusic, A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer, J. Combin. Theory Ser. B 88 (2003), 67-76.
[5]	C. Delorme, Cayley digraphs and graphs, European J. Combin. 34 (2013), 1307-1315.
[6]	J. D. Dixon and B. Mortimer, Permutation Groups, Springer-Verlag, New York, 1996.
[7]	P. G. Doyle, On transitive graphs, Senior Thesis, Harvard College, 1976.
[8]	Y. Q. Feng, J. H. Kwak, M. Y. Xu and J. X. Zhou, Tetravalent half-arc-transitive graphs of order p4, Eur. J. Comb. 29 (2008), 555-567.
[9]	D. Firth, An algorithm to find normal subgroups of a finitely presented group up to a given index, PhD Thesis, University of Warwick, 2005.
[10] D. F. Holt, A graph which is edge transitive but not arc transitive, J. Graph Theory 5 (1981), 201-204.
162
Ars Math. Contemp. 8 (2015) 149-162
[11]	A. Malnic and D. Marusic, Constructing 2 -transitive graphs of valency 4 and vertex stabilizer Z2 x Z2, Discrete Math. 245 (2002), 203-216.
[12]	A. Malnic, D. Marusic, P. Potocnik, Elementary abelian covers of graphs, J. Alg. Combin. 20
(2004),	71-97.
[13]	A. Malnic, R. Nedela and M. Skoviera, Lifting graph automorphisms by voltage assignments, Eur. J. Comb., 21 (2000), 927-947.
[14]	D. Marusic, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser.B 73 (1998), 41-76.
[15]	D. Marusic, Recent developments in half-transitive graphs, Discrete Math. 182 (1998), 219231.
[16]	D. Marusic, Quartic half-arc-transitive graphs with large vertex stabilizers, Discrete Math. 299
(2005),	180-193.
[17]	D. Marusic and R. Nedela, On the point stabilizers of transitive permutation groups with non-self-paired suborbits of length 2, J. Group Theory 4 (2001), 19-43.
[18]	P. Potocnik, P. Spiga, G. Verret, A census of arc-transitive digraphs of valence 2 and tetravalent graphs admitting a 1 -arc-transitive group action, Ars. Math. Contemp. 8 (2015), 133-148.
[19]	P. Potocsnik, G. Verret, On the vertex-stabiliser in arc-transitive digraphs, J. Combin. Theory Ser. B. 100 (2010), 497-509.
[20]	R. PoZar, Sectional split extensions arising from lifts of groups, Ars. Math. Contemp. 6 (2013), 393-408.
[21]	W. T. Tutte, Connectivity in graphs, University of Toronto Press, Toronto, 1966.
[22]	H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.
[23]	S. Wilson, Rose window graphs, Ars Mathematica Contemporanea 1 (2008), 7-19.
[24]	S. Wilson, A census of edge-transitive tetravalent graphs, http://jan.ucc.nau.edu/ ~swilson/C4Site/BigTable.html.