¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 343-353
Half-arc-transitive graphs of prime-cube order of small valencies*
Yi Wang , Yan-Quan Feng t
Department of Mathematics, Beijing Jiaotong University, Beijing, P.R. China
Received 30 October 2015, accepted 25 November 2016, published online 20 March 2017 Abstract
A graph is called half-arc-transitive if its full automorphism group acts transitively on vertices and edges, but not on arcs. It is well known that for any prime p there is no half-arc-transitive graph of order p or p2. In 1992, Xu classified half-arc-transitive graphs of order p3 and valency 4. In this paper we classify half-arc-transitive graphs of order p3 and valency 6 or 8. In particular, the first known infinite family of half-arc-transitive Cayley graphs on non-metacyclic p-groups is constructed.
Keywords: Cayley graph, half-arc-transitive graph, automorphism group. Math. Subj. Class.: 05C10, 05C25, 20B25
1 Introduction
A (di)graph r consists of a pair of sets (V(r), E(r)), where V(r) is its vertex set, and E(r) is its edge set. For a graph, E(r) is also called undirected edge set and is a subset of the set {{u,v} | u, v G V(r)}, and for a digraph, E(r) is also called directed edge set and is a subset of the set {(u, v) | u, v G V(r)}. For an edge {u,v} of a graph r, we call (u, v) an arc of r. An automorphism of a (di)graph r is a permutation on V(r) preserving the adjacency of r, and all automorphisms of r form a group under the composition of permutations, called the full automorphism group of r and denoted by Aut(r). A (di)graph r is vertex-transitive or edge-transitive if Aut(r) acts transitively on V(r) or E(r), respectively. A graph r is arc-transitive or symmetric if Aut(r) is transitive on the arc set of r, and half-arc-transitive provided that it is vertex-transitive, edge-transitive, but not arc-transitive. Throughout this paper, all (di)graphs r are finite and simple, that is, | V(r) | is finite and there are no loops or multiple edges.
*This work was supported by the National Natural Science Foundation of China (11231008, 11571035) and by the 111 Project of China (B16002).
t Corresponding author
E-mail addresses: yiwang@bjtu.edu.cn (Yi Wang), yqfeng@bjtu.edu.cn (Yan-Quan Feng)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
343
Ars Math. Contemp. 13 (2017) 275-291
Let G be a permutation group on a set Q and a e Q. Denote by Ga the stabilizer of a in G, that is, the subgroup of G fixing the point a. We say that G is semiregular on Q if Ga = 1 for every a e Q and regular if G is transitive and semiregular.
Let G be a finite group and S a subset of G such that 1 e S. The Cayley digraph r = Cay(G, S) on G with respect to S is defined as the digraph with vertex set V(r) = G and directed edge set {(g, sg) | g e G, s e S}. The Cayley digraph Cay(G, S) is connected if and only if G = (S}, and if S is symmetric, that is, S-1 = {s-1 | s e S} = S, then Cay(G, S) can be viewed as a graph by identifying the two oppositely directed edges (g, sg) and (sg, g) as an undirected edge {g, sg}. Thus a Cayley graph can be viewed as a special case of a Cayley digraph. It is easy to see that Aut(Cay(G, S)) contains the right regular representation G = {g | g e G} of G, where g is the map on G defined by x ^ xg, x e G, and G is regular on the vertex set V(r). This implies that a Cayley digraph is vertex-transitive. Also, it is easy to check that Aut(G, S) = {a e Aut(G) | Sa = S} is a subgroup of Aut(Cay(G, S))1, the stabilizer of the vertex 1 in Aut(Cay(G, S)). A Cayley digraph Cay(G, S) is said to be normal if G is normal in Aut(Cay(G, S)).
In 1966, Tutte [26] initiated an investigation of half-arc-transitive graphs by showing that a vertex- and edge-transitive graph with odd valency must be arc-transitive. A few years later, in order to answer Tutte's question of the existence of half-arc-transitive graphs of even valency, Bouwer [5] gave a construction of a 2k-valent half-arc-transitive graph for every k > 2. Following these two classical articles, half-arc-transitive graphs have been extensively studied from different perspectives over decades by many authors. See, for example, [3, 13, 15, 18, 20, 23, 25, 33]. One of the standard problems in the study of half-arc-transitive graphs is to classify such graphs of certain orders. Let p be a prime. It is well known that there are no half-arc-transitive graphs of order p or p2, and by Cheng and Oxley [6], there are no half-arc-transitive graphs of order 2p. Alspach and Xu [2] classified half-arc-transitive graphs of order 3p and Dobson [9] classified half-arc-transitive graphs of order a product of two distinct primes. Classification of half-arc-transitive graphs of order 4p had been considered for more than 10 years by many authors, and recently was solved by Kutnar et al. [16]. Despite all of these efforts, however, further classifications of half-arc-transitive graphs with general valencies seem to be very difficult.
In view of the fact that 4 is the smallest admissible valency for a half-arc-transitive graph, special attention has rightly been given to the study of tetravalent half-arc-transitive graphs. In particular, constructing and classifying tetravalent half-arc-transitive graphs is currently an active topic in algebraic graph theory (for example, see [10, 11, 22, 28]). Marusic [20] and Sparl [27] classified tightly attached tetravalent half-arc-transitive graphs with odd and even radius, respectively. For quite some time, all known examples of tetravalent half-arc-transitive graphs had vertex-stabilizers that are either abelian or dihedral: For instance, Marusic [21] constructed an infinite family of tetravalent half-arc-transitive graphs having vertex stabilizers isomorphic to Z™ for each positive integer m > 1, and Conder and Marusic [7] constructed a tetravalent half-arc-transitive graph with vertex-stabilizer isomorphic to D4 of order 8. Recently, a tetravalent half-arc-transitive graph with vertex-stabilizers that are neither abelian nor dihedral was constructed by Conder et al. [8].
Xu [31] classified tetravalent half-arc-transitive graphs of order p3 for each prime p, and later this was extended to the case of p4 by Feng et al. [10]. In this paper, we classify half-arc-transitive graphs of order p3 and valency 6 or 8. In these new constructions, there is an infinite family of half-arc-transitive Cayley graphs on non-metacyclic p-groups, and to our best knowledge, this is the first known construction of such graphs.
Y. Wang and Y.-Q. Feng: Half-arc-transitive graphs of prime-cube order of small valencies 345
Denote by Zn the cyclic group of order n as well as the ring of order n. From elementary group theory we know that up to isomorphism there are only five groups of order p3, that is, three abelian groups Zp3, Zp2 x Zp and Zp x Zp x Zp, and two non-abelian groups G1 (p) and G2 (p) defined as
Gi(p) = (a, b | ap2 = 1, bp = 1,b-1ab = a1+p)
and
G2(p) = (a, b, c | ap = bp = cp = 1, [a, b] = c, [a, c] = [b, c] = 1).
It is easy to check that the center of G1(p) is (ap) and the center of G2(p) is (c).
Denote by the multiplicative group of the ring Zn consisting of numbers coprime to
n. Let e be an element of order j < p in Z*2. Since Zp2 = Zp(p-1), we have j | (p -1). For
each k € Z;,let Tj'fc = {bk a,bk ae,..., bV-1, (bk a)-1, (bk ae)-1,..., (bk aej-1 )-1} be a subset of G1 (p) and define
rj,k (p) = Cay(G1 (p), T).
By Proposition 2.2, rj,fc (p) does not depend on the choice of the element e of order j. Suppose 4 | (p - 1) and let A be an element of order 4 in Zp. For each k € Zp with
k = 2-1(1 + A), let S4,fc = {a,b,aAbA-1ck, a-A-1b-Ac1-k, a-1,b-1, (aAbA-1ck)-1, (a-A-1b-Ac1-k)-1} be a subset of G2(p) and define
r4,fc (p) = Cay(G2(p),S4,fc).
There are exactly two elements of order 4 in Zp, that is, A and A-1 = -A. Let
S4,s = {a, b, a-Ab-A-1cs, aA-1bAc1-s, a-1, b-1, (a-Ab-A-1cs)-1, (aA-1bAc1-s)-1},
where s € Zp and s = 2-1(1-A). For each k € Zp and k = 2-1(1+A), the automorphism of G2(p) induced by a ^ a, b ^ aA-1bAc1-k+A, c ^ cA, maps S4,k to S4,k-A, and so Cay(G2(p), S4,k) = Cay(G2(p), S4jfc-A). Since k = 2-1(1 + A), we have k - A = 2-1(1 - A). Thus, r4,k(p) does not depend on the choice of A. The following is the main result of the paper.
Theorem 1.1. Let r be a graph of order p3 for a prime p. Then we have:
(1)	If r has valency 6 then r is half-arc-transitive if and only if 3 | (p - 1) and r = r3,k(p). There are exactly (p - 1)/2 nonisomorphic half-arc-transitive graphs of the form r3,k(p);
(2)	If r has valency 8 then r is half-arc-transitive if and only if 4 | (p - 1) and r = r4,k(p) or r4,k (p). There are exactly p -1 nonisomorphic half-arc-transitive graphs of the forms r4'fc (p) and r4,k (p), with (p - 1)/2 such graphs in each form.
2 Preliminaries
We start by stating some group-theoretical results. For a group G and x, y € G, denote by [x, y] the commutator x-1y-1xy and by xy the conjugation y-1xy. The following proposition is a basic property of commutators and its proof is straightforward (also see [24, Subsection 5.1.5]):
346
Ars Math. Contemp. 13 (2017) 275-291
Proposition 2.1 ([14, Kapitel III, Hilfssatze 1.2 and 1.3]). Let G be a group. Then, for any
x,y, z G G, we have [x,y] = [y,x]-1, [xy, z] = [x, z]y[y, z] and [x, yz] = [x, z][x,y]z. Furthermore, if [x, y] commutes with x and y then for any integers i and j, [x®, yj] = [x, y]ij, and for any positive integer n, (xy)" = x"y"[y, x]( 2).
We remark that it is easy to see that the equality (xy)" = x"y"[y,x]W holds also for negative integers n if we define (") = "("2-1). By Li and Sim [18, Theorem 1.1 and Lemma 2.6], we have the following proposition.
Proposition 2.2. Let r be a Cayley graph on G1(p) of valency 2j with 1 < j < p. Then r is half-arc-transitive if and only if j|(p — 1) and r = Tj,k (p) for 1 < k < p — 1, and
rj'fc (p) = rj 'k (p) if and only if j = j and k = k (mod p). Furthermore, for each j | (p — 1) there exist exactly (p — 1)/2 nonisomorphic such graphs of the form Tj'k (p).
Since a transitive permutation group of prime degree p has a regular Sylow p-subgroup, every vertex-transitive digraph of order a prime must be a Cayley digraph. Together with the results given by Marusic [19], we have the following proposition.
Proposition 2.3. Any vertex-transitive digraph of order pk with 1 < k < 3 is a Cayley digraph on a group of order pk.
For any abelian group H, the map h ^ h-1, h G H is an automorphism of H. By [10, Proposition 2.10], we have the following proposition.
Proposition 2.4. Let G be a finite group and Cay(G, S) a connected half-arc-transitive Cayley graph. Then, S does not contain an involution and for any s G S, there is no a G Aut(G, S) satisfying sa = s-1. Furthermore, every edge-transitive Cayley graph on an abelian group is also arc-transitive.
The following proposition is about isomorphisms between Cayley graphs on p-groups.
Proposition 2.5 ([17, Theorem 1.1 (3)]). Let Cay(G, S) and Cay(G, T) be two connected Cayley graphs on a p-group G with respect to subsets S and T, and let |S | = |T | < 2p. Then Cay(G, S) and Cay(G, T ) are isomorphic if and only if there is an automorphism a of G such that Sa = T.
Let r = Cay(G, S) be a Cayley digraph on a finite group G. By Godsil [12, Lemma 2.2] (also see [32, Proposition 1.5]), we have NAutr(G) = G xi Aut(G, S).
Proposition 2.6. A Cayley digraph r = Cay(G, S) is normal if and only if Aut(r)1 = Aut(G, S).
A finite group G is called 2-genetic if each normal subgroup of G can be generated by two elements. For a prime p, denote by Op (G) the largest normal p-subgroup of G, and by $(G) the Frattini subgroup of G, that is, the intersection of all maximal subgroups of G. We call G a p'-group if the order of G is not divisible by p. The following proposition is about automorphism groups of Cayley digraphs on 2-genetic groups.
Proposition 2.7 ([30, Theorem 1.1]). Let G be a nonabelian 2-genetic group of order p" for an odd prime p and a positive integer n, and let r = Cay(G, S) be a connected Cayley digraph. Assume that Aut(G, S) is a p'-group and r is non-normal. Then p G {3,5, 7,11}
Y. Wang and Y.-Q. Feng: Half-arc-transitive graphs of prime-cube order of small valencies 347
and ASL(2,p) < Aut(r)/$(OP(A)) < AGL(2,p). Furthermore, the kernel of A := Aut(r) acting on the quotient digraph r$(Op(A)) is $(Op(A)), and one of the following happens:
(1)	p = 3, n > 5, and r$(Op(A)) has out-valency at least 8;
(2)	p = 5, n > 3 and r$(Op(A)) has out-valency at least 24;
(3)	p = 7, n > 3 and r$(Op(A)) has out-valency at least 48;
(4)	p = 11, n > 3 and r$(Op(A)) has out-valency at least 120.
In Proposition 2.7, the quotient digraph r$(Op(A)) has the orbits of $(Op(A)) on V(r) as vertices, and for two orbits O1 and O2, (Oi, O2) is a directed edge in r$(Op(A)) if and only if (u, v) is a directed edge in r for some u e O1 and v e O2.
3 Proof of Theorem 1.1
Let r be a half-arc-transitive graph and A = Aut(r). Let (u, v) be an arc of r and set (u,v)A = {(u°,va) | a e A}. Define digraphs r1 and r2 having vertex set V(r) and directed edge sets (u, v)A and (v, u)A, respectively. Since r is half-arc-transitive, for every edge {x, y} G E(r), each of r1 and r2 contains exactly one of the directed edges (x, y) and (y, x), and r is connected if and only if r® is connected for each i = 1,2. Furthermore, A = Aut(r®) and r® is A-edge-transitive. In what follows we denote by one of the digraphs r1 and r2.
Let r be a half-arc-transitive graph of order p3 for a prime p. Since there exists no half-arc-transitive graph of order less than 27 (see [1]), we have p > 3. By Proposition 2.3, r = Cay(G, S) and r = Cay(G, R). Since a group of order p or p2 is abelian and there is no half-arc-transitive Cayley graph on an abelian group by Proposition 2.4, r is connected, and so G = (R) and S = R U R-1. Furthermore, G = G1(p) or G2(p), where
G1(p) = (a,b | ap2 = 1,bp = 1,b-1ab = a1+p),
G2(p) = (a, b, c | aP = bp = cp = 1, [a, b] = c, [a, c] = [6, c] = 1).
Since G = (R) is non-abelian, R contains two elements x and y such that xy = yx, and since |G| = p3, we have (x, y) = G. For G = G2 (p), x and y have the same relations as do a and b, which implies that we may assume that a, b e R. Similarly, for G = G1 (p) we may assume that a G R. Thus we have the following observation:
Observation 3.1. Let r be a half-arc-transitive graph of order p3 for a prime p. Then r = Cay(G, S) and = Cay(G, R), where G = G1(p) or G2(p) with p > 3, G = (R) and S = R U R-1. Furthermore,
(1)	if G = G1(p) then a e R;
(2)	if G = G2(p) then a, b G R.
Let us begin by considering normal half-arc-transitive Cayley graphs on G2(p) of valency 8. Since G2(p) has center (c), Proposition 2.1 implies bja® = a®bjc-ij and (a®bj)k = akibkjc-2 k(k-1)ij for i,j, k G Zp. Our proofs will constantly be relying on these facts.
348
Ars Math. Contemp. 13 (2017) 275-291
Lemma 3.2. Let r = Cay(G2(p), S) be a Cayley graph of valency 8. Then r is normal and half-arc-transitive ifandonly if 4|(p — 1) and r = r4,k (p) for some k.
Proof. Let r = Cay(G2(p),S) be normal and half-arc-transitive. Set A = Aut(r). By Observation 3.1, we have 1 = Cay(G2(p),R) with p > 3, G2(p) = (R) and S = RU R-1. We may further assume a, b, a®6jck G R. Since r has valency 8, we have |S| = 8 and |R| = 4. Since r is normal, Proposition 2.6 implies that A1 = Aut(G2(p),S) = Aut(G2(p), R), which is transitive on R. Since |R| = 4, Aut(G2(p),R) < S4. Thus, Aut(G2 (p), R) has a regular subgroup M on R such that M = Z2 x Z2 or Z4.
Case 1: M = Z2 x Z2. Let «1,^2 G Aut(G2(p),R) and M = (ai) x («2) = Z2 x Z2. Without loss of generality, we may assume that aai = b and ba1 = a, and so cai = c-1. This yields that R = {a, b, a®bjck, (a®bjck)ai} = {a, b, a®bjck, ajb®c—ij—k}. Since (a1, a2) = Z2 x Z2, we may assume that a°2 = a®bjck and (a®bjck)a2 = a. Then
- - - - r	-2-2
ba2 = ajb®c—ij—k and so ca2 = c® — j . By Proposition 2.1,
a = (a®bj ck )a2 = (a®bj ck )®(aj b®c—ij—k )j (/—j2 )k = (a®bj )®(aj b®)j ck(i2—j2+i—j)—ij2 = ai2b®jc 2—1i2j(i 1)aj2b®jc—2-1ij2(j—1)ck(i2—j2+i—j)—ij2 = ai2+j2 b2ijc—ij3 + k(i2 —j2+i—j)—¿j2 — 2 — 1i2j(i — 1) — 2 — 1ij2(j — 1),
implying the following equations:
i2 + j2 = 1;	(3.1)
2 ij = 0;	(3.2)
—ij3 + k(i2 — j 2 + i — j) — ij2 — 2—1 i2 j (i — 1) — 2—1 ij2 ( j — 1) = 0.	(3.3)
As above, in what follows all equations are considered in Zp, unless otherwise stated. Since a1 interchanges a and b, we can assume i = 0 by Eq. (3.2), and so j = ±1 by Eq. (3.1). If j = —1 then S = {a, b, a—1c—k, b—1ck} U {a—1, b—1, ack, bc—k}, and the automorphism of G2(p) induced by a 1 a—1, b 1 bc— k, c 1 c—1, fixes S setwise, contrary to Proposition 2.4. If j = 1 then k = 0 by Eq. (3.3), implying that a®bjck = b, a contradiction.
Case 2: M = Z4. Let a G Aut(G2(p),R) and M = (a) = Z4. Then R = {a, aa, aa , aa }, and since G2(p) = (R), we have (a, aa) = G2(p) and so a 1 a, b 1 aa induces an automorphism of G2(p). We thus assume that aa = b, and a is induced by a 1 b, b 1 a®bj ck, c 1 c—¿. It follows that
R = {a, b, aVck, aijbi+j2c—i2j+k(j—i)—2-1ij2(j—1)}.
Since
= aa4 = ai(i+j2 ) bj(2i+j2 ) c®3 j + (k—i2 j)(i+j2 )—¿k(j—i)+2-1i2 j2 (j — 1) —2 — 1ij(i+j2 )(i+j2 — 1)
(®+j2 )bj(2i+j2)ck(i2 + j2 +i—¿j)— ¿2j3 + 2-1ij[ij2— ij — (i+j2)(i+j2 — 1)]
= a b	c
we have the following equations
i(i + j2) = 1; (3.4)
j (2i + j2) = 0; (3.5)
k(i2 + j2 + i — ij) — i2j3 + 2—1 ij [ij2 — ij — (i + j2)(i + j2 — 1)] = 0. (3.6)
Y. Wang and Y.-Q. Feng: Half-arc-transitive graphs of prime-cube order of small valencies 349
By Eq. (3.5), either j = 0 or 2i + j2 = 0.
Case 2.1: j = 0. By Eq. (3.4), i = ±1. If i = 1 then k = 0 by Eq. (3.6), and hence a®bjck = a, a contradiction. If i = —1 then S = {a, b, a-1ck, b-1ck} U {a-1, b-1, ac-k, bc-k }, and the automorphism of G2(p) induced by a ^ a-1, b ^ bc-k, c ^ c-1, fixes S setwise, contrary to Proposition 2.4.
Case 2.2: 2i + j2 = 0. Clearly, i + j2 = —i. By Eq. (3.4), i2 = —1 and so ij2 = 1 — i2 = 2. Since j2 = — 2i, Eq. (3.6) implies 2k(1 + i + ij) = —ij (1 + i + ij), and hence 2ki(1 + i + ij) = j(1 + i + ij), implying 2ki — j =0 or 1 + i + ij = 0.
Suppose 2ki — j =0. Then ij = —2k and k = —2-1ij. Since ij2 = 2, we have k = —j-1 and k(j—i)+1 = —k(j+i) —1. It follows that S = {a,b,a4bj ck ,a-2k b-icfc(j-i)+1} U {a-1, b-1, a-ib-jck, a2kb®c-fc(j+i)-1}. The automorphism of G2(p) induced by a ^ a-1, b ^ b-1, c ^ c, fixes S setwise, contrary to Proposition 2.4.
Thus, 1 + i + ij = 0 and so j = i — 1. Then S = {a, b, a4bi-1cfc, a-i-1b-ic1-k} U {a-1, b-1, a-ib1-ic-fc+1+i, ai+1bick-i}. If k = 2-1(1 + i), then k = —k + 1 + i and 1 — k = k — i, and hence the automorphism of G2(p) induced by a ^ a-1, b ^ b-1, c ^ c, fixes S setwise, contrary to Proposition 2.4. Hence k = 2-1(1 + i). Note that i2 = —1 implies that 4 | (p — 1) and i = A is an element of order 4 in Zp. Then j = A — 1 and k = 2-1(1 + A). By the definition of r4 k(p) before Theorem 1.1, T = r4 k(p).
To finish the proof, we only need to show that r4,k(p) = Cay(G2(p), S4,k) is normal and half-arc-transitive. Note that S4,k = {a, a-1, b, b-1, aAbA-1ck, a-Ab1-Ac-fc+A+1, a-A-1b-Ac1-k, aA+1bAck-A}, A is an element of order 4 in Zp, and k = 2-1(1 + A). Let A = Aut(r4jfc(p)) and set R4jfc = {a,b, aAbA-1ck, a-A-1b-Ac1-k}. Then S4jfc = R4jfc U . Let a be the automorphism of G2(p) induced by a ^ b, b ^ aAbA-1ck, c ^ c-A. By Proposition 2.1, (aAbA-1ck)a = a-A-1b-Ac1-k and (a-A-1b-Ac1-k)a = a. Thus, a G Aut(G2(p), S4,k) has order 4 and permutes the elements of R4,k cyclically, implying that G2(p) x (a) is half-arc-transitive on r4,k (p). To prove the normality and the half-arc-transitivity of r4,k(p), it suffices to show that A = G2(p) x (a).
Write L = Aut(G2(p), S4 k). Then L acts on S4 k faithfully. Set Q1 = {a, a- -1}, ^2 = {b,b-1}, Q3 = {aAbA-1ck,a-Ab1-Ac-fc+A+1}, Q4 = {a-A-1 b-Ac1-k, aA+1bAcfc-A}. Since L < Aut(G2(p)), {Q^ Q2, Q3, Q4} is a complete imprimitive block system of L on S4,k. Let Q = {Q1, Q2, Q3, Q4}. Since a G L, L is transitive on Q.
Claim: La = 1 and Lx = 1 for any x G S4,k. Let ft G La. Then af = a and Qf = Q1. Thus, (Q2 U Q3 U Q4)f = Q2 U Q3 U Q4, and so bf G Q2 U Q3 U Q4, that is, bf = b, b-1, aAbA-1ck, a-Ab1-Ac-k+A+1, a-A-1b-Ac1-k or aA+1bAck-A. As A is an element of order 4 in Zp, we have A = 0, ±1. If bf = b-1 G Q2 then cf = c-1 and Qf = Q2. It follows that (Q3 U Q4)f = Q3 U Q4, implying that (aAbA-1ck)f = aAb1-Ac-k G Q3 U Q4, which is impossible. If bf = aAbA-1ck G Q3 then cf = cA-1 and Qf = Q3. Thus, Qf C Q2 u Q4, but (aAbA-1ck)f = a-1b-2Ac-A+2+2fc(A-1) G Q2 U Q4, a contradiction. If bf = a-Ab1-Ac-k+A+1 G Q3, then cf = c1-A and Qf = Q3. Thus, Qf C Q2 U Q4 and (aAbA-1ck)f = a2A+1b2Ac-A-2fc(A-1) implies that (aAbA-1ck)f = b-1. It follows that Qf = Q2 and so Qf = Q4, which is impossible because (aA+1bAcfc-A)f = aA+2bA+1c-2kA+k-A-2 G Q4. If bf = a-A-1b-Ac1-k G Q4, then cf = c-A and Qf = Q4. Thus, Qf C Q2 u Q3 and (aAbA-1 ck)f = aA+2bA+1c-2fcA+fc-A-2 implies that (aAbA-1ck)f = b-1 and A = —2. It follows that Qf = Q2 and so Qf = Q3. This forces A = 2 as (aA+1bAck-A)f = a2bc-2kA+A-2 G Q3, and hence A = 2 = —2, a contradiction. If bf = aA+1bAcfc-A G Q4 then cf = cA and Qf = Q4. Thus, Qf C Q2 U Q3
350
Ars Math. Contemp. 13 (2017) 275-291
and so (aAbA-1ck= aA-2b-A-1c2kA-k-A g q2 u Q3, which is impossible. The above arguments mean that b^ = b, implying ft =1. Thus, La = 1, and since Q1 is a block of L, we have La-i < La = 1. The transitivity of (a) on Q implies Lx = 1 for any x g S4,k, as claimed.
Let K be the kernel of L on Q. Then K fixes each Qj setwise, and by Claim, |K | = 2. Suppose |K| = 2. Then the unique involution, say 7, in K interchanges the two elements in each Qj because Lx = 1. In particular, 7 is induced by aY = a-1, bY = b-1 and cY = c. It follows that (aAbA-1ck)Y = a-Ab1-Ack, and since (aAbA-1ck)Y g Q3, we have a-Ab1-Ack = a-Ab1-Ac-fc+A+1, forcing that k = 2-1(1 + A), a contradiction. Thus, K = 1 and L < S4, the symmetric group of degree 4.
Since Lx = 1 for any x g S4,k, L is semiregular on S4,k, and so |L| is a divisor of 8. Since a g L, we have |L| =4 or 8. Suppose |L| = 8. Since L < S4, L is the dihedral group of order 8, and so a2 g Z(L). Note that a2 interchanges Q1 and Q3, and Q2 and Q4. Then Lq1 = L^ = Lq3 . Since L is transitive on Q, |Lq1 | = 2. Let S be the unique involution in Lq1 . Then Qf = Q1 and Q3 = Q3. Since La = 1, we have a5 = a-1, and since K = 1, we have Q2 = Q4. On the other hand, (a) < L and so R4,k is an imprimitive block of L, yielding R4 k = R-J. It follows that b5 g Q2 n R4 k = Q4 n R-k, that is, b5 = aA+1bAcfc-A. Thus, c5 = c-A, and since S is an involution, b = (aA+1bAcfc-A)5 = a-2b-1c-1, which is impossible. Thus, |L| = 4 and L = (a). Clearly, p \ |L| = |Aut(G2(p), S4,k)|. By Proposition 2.7, r4,k(p) is a normal Cayley graph, and by Proposition 2.6, A = G2 (p) x (a).	□
Remark 3.3. The above proof implies Aut(r4 k(p)) = G2(p) x (a) andAut(r4k(p))1 = Aut(G2(p), S4,k) = (a), where a is the automorphism of G2(p) of order 4 induced by a ^ b and b ^ aAbA-1ck. Moreover, the automorphism a cyclically permutes the elements in
{a, b, aAbA-1ck, a-A-1b-Ac1-k}.
Lemma 3.4. There are exactly (p — 1)/2 nonisomorphic graphs of the form r4,k (p).
Proof. By definition, S4,k = {a, a-1, b, b-1, aAbA-1ck, a-Ab1-AcA-fc+1, a-A-1b-Ac1-k, aA+1bAck-A} and r4,k(p) = Cay(G2(p), S4,k), where A is an element of order 4 in Zp, k g Zp with k = 2-1(1 + A). Thus, 4 | (p — 1). Since r4,k(p) does not depend on the choice of A (see the paragraph before Theorem 1.1), there are at most p — 1 nonisomorphic half-arc-transitive graphs of the form r4,k(p) (k = 2-1(1 + A)). To finish the proof, it suffices to show that r4 k(p) = r4 i(p) (k, l = 2-1(1 + A)) if and only if l = k or l = 1 + A — k.
Let l = 1 + A — k. One may easily show that the automorphism of G2(p) induced by
a ^ a-1, b ^ b-1, c ^ c, maps S4,k to S4,1+A-k = S4jl, and so r4,k(p) = r4jl(p). Let r4,k(p) = ^(p) (k,1 = 2-1(1 + A)). Set
R4ji = {a, b, aAbA-1cj,a-A-1b-Ac1-i}.
Then S4,k = R4,k U R-k and S4ji = R4ji U R-1. Since 4 | (p — 1), we have p > 5, and by Proposition 2.5, there exists a g Aut(G2(p)) such that k = S4jl. This implies that a maps the stabilizer Aut(r4,k(p))1 to the stabilizer Aut(r4jl(p))1. It follows Aut(G2(p),S4,k)ff = Aut(G2(p),S4,i) because Aut(r4,k(p))1 = Aut(G2(p), S4,fc) and Aut(r4jl(p))1 = Aut(G2(p), S4jl) by Remark 3.3. Moreover, Aut(G2(p), S4,k) is regular on both R4 k and R-J, and Aut(G2(p), S4 i) is regular on both R4ji and R-1.
Y. Wang and Y.-Q. Feng: Half-arc-transitive graphs of prime-cube order of small valencies 351
Thus, = R4jl or R- ^ and replacing a by a multiplication of a and an element
in Aut(G2(p),S4jI), we may assume that aCT = a if RJ k = R4jl, and aCT = a-1 if
OCT _ D-1
R4,fc = R4,l .
Assume R4 k = R4jl with aCT = a. Then bCT G R4jl and bCT = b, aAbA-1c' or a-A-16-Ac1-1. If bCT = aAbA-V then = cA-1. By Proposition 2.1, (aAbA-1ck)CT = a-1&-2Ac-A+2+(fc+I)(A-1) G R4 ,;, which is impossible. If bCT = a^^b^c1-1 then cCT = c-A, and hence (aAbA-1ck)CT = aA+26A+1c4A424l(A4l)4fcA G R4 ,;, which is impossible. If bCT = b then cCT = c, and hence (aAbA-1ck)CT = aAbA-1ck G R4jl, implying that l = k.
Assume R^ = R-1 with aCT = a-1. Then bCT G R^and bCT = b-1, a-Ab1-Ac-I+A+1 or aA+1bAcI-A. If bCT = a-Ab1-Ac-I+A+1 then cCT = cA-1. By Proposition 2.1, we have (aAbA-1ck)CT = ab2Ac4A+(fc4')(A41) G R-1, which is impossible. If bCT = aA+1bAcI-A then cCT = c-A and hence (aAbA-1ck)CT = a-A-2b-A-1c-A-fcA+I(A-1) G R-1, which is impossible. If bCT = b-1 then we have cCT = c and (aAbA-1ck)CT = a^b1-^ G R-1, implying that l = 1 + A - k.	□
By Magma [4], a brute force computer search can be performed to verify the following lemma, but we have also verified the correctness of the lemma theoretically. Since the proof is rather long, we will not present it in the paper but are willing to provide it upon request (also see [29]).
Lemma 3.5. There is no half-arc-transitive graph of order 27 and valency 6 or 8.
Now we are ready to prove Theorem 1.1.
Proof of Theorem 1.1. Let r be a half-arc-transitive graph of order p3 and valency 6 or 8, and let A = Aut(r). By Observation 3.1, r = Cay(G, S) and r = Cay(G, R) for some group G = G1(p) or G2(p) with p > 3, where G = (R) and S = R U R-1. By Lemma 3.5, p > 5, and by the half-arc-transitivity of r, A = Aut(lT) and A1 is transitive on R. Since G = (R), Aut(G, R) acts faithfully on R, and since |R| < 5, Aut(G, R) is a p'-group. Since G is a non-abelian group of order p3, G is 2-genetic, that is, each normal subgroup of G can be generated by two elements. By Proposition 2.7,1 is normal, and by Proposition 2.6, A1 = Aut(G, R). Since A = Aut(r) = Aut^), we have A1 = Aut(G, S), and so r is normal.
The theorem is true for G = G1(p) by Proposition 2.2. Now assume G = G2(p). If r has valency 8, the theorem is also true by Lemma 3.2. We may thus assume that r has valency 6, that is, | R| = 3. We prove that this is not possible.
By Observation 3.1, R = {a, b, a®bjck}, where i, j, k G Zp. Since Aut(G, R) is transitive on R, there exists a G Aut(G2(p)) of order 3 permuting the elements in R cyclically. If necessary, replace a by a2, and then we may assume that a is induced by a 1 b, b 1 a®bjck, and then c 1 c- by Proposition 2.1. Thus, a = (a®bjck)a = aijbi+j2c-^'-2-1 ij2O'^+Kj-O, and so we have:
ij = 1; i + j2 = 0; -i2j + k(j - i) - 2-1ij2(j - 1)=0.
(3.7)
(3.8)
(3.9)
353	Ars Math. Contemp. 13 (2017) 275-291
By Eqs. (3.7) and (3.8), j3 + 1 = 0, implying (j + 1)(j2 - j + 1) =0. Thus, either j + 1=0 or j2 - j + 1 = 0. If j + 1 = 0 then j = -1. By Eq. (3.8), i = -1 and so S = {a, b, a-1b-1ck} U {a-1, b-1, abc-1-k}, but the automorphism of G induced by a ^ a-1, b ^ abc-1-k, c ^ c-1, fixes S setwise, contrary to Proposition 2.4. If j2 - j + 1 =0 then by Eq. (3.8), i = 1 - j, and since ij = 1, Eq. (3.9) implies that -i + k(j - i) - 2-1j(j - 1) = j - 1 + k(j + j - 1) + 2-1 = (2j - 1)(k + 2-1) = 0. It follows that either 2j - 1 =0 or k + 2-1 =0. For 2j - 1 = 0, we have j = 2-1 and i = 1 - j = 1 - 2-1 = 2-1, but then Eq. (3.7) implies 4 = 1 in Zp, contradicting p = 3. For k + 2-1 = 0, we have S = {a,b,a1-j bj c-2-1} U {a-1, b-1, aj-1b-j c-2-1}, and the automorphism of G induced by a ^ a-1, b ^ b-1, c ^ c, fixes S setwise, a contradiction.	□
References
[1]	B. Alspach, D. Marusic and L. Nowitz, Constructing graphs which are 1/2-transitive, J. Austral. Math. Soc. Ser. A 56 (1994), 391-402, doi:10.1023/a:1022466626755.
[2]	B. Alspach and M. Y. Xu, 1/2-transitive graphs of order 3p, J. Algebraic Combin. 3 (1994), 347-355, doi:10.1023/a:1022466626755.
[3]	I. Antoncic and P. Sparl, Classification of quartic half-arc-transitive weak metacirculants of girth at most 4, Discrete Math. 339 (2016), 931-945, doi:10.1016/j.disc.2015.10.015.
[4]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: the user language, J. Symbolic Comput. 24 (1997), 235-265, doi:10.1006/jsco.1996.0125.
[5]	I. Z. Bouwer, Vertex and edge transitive but not 1-transitive graphs, Canad. Math. Bull. 13 (1970), 231-237, doi:10.4153/cmb-1970-047-8.
[6]	Y. Cheng and J. Oxley, On weakly symmetric graphs of order twice a prime, J. Combin. Theory Ser. B 42 (1987), 196-211, doi:10.1016/0095-8956(87)90040-2.
[7]	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, doi:10.1016/S0095-8956(02)00036-9.
[8]	M. D. E. Conder, P. Potocnik and P. Sparl, Some recent discoveries about half-arc-transitive graphs, Ars Math. Contemp. 8 (2015), 149-162, http://amc-journal.eu/index. php/amc/article/view/557.
[9]	E. Dobson, Automorphism groups of metacirculant graphs of order a product of two distinct primes, Combin. Probab. Comput. 15 (2006), 105-130, doi:10.1017/S0963548305007066.
[10]	Y.-Q. Feng, J. H. Kwak, X. Wang and J.-X. Zhou, Tetravalent half-arc-transitive graphs of order p4, European J. Combin. 29 (2008), 555-567, doi:10.1016/j.ejc.2007.05.004.
[11]	Y.-Q. Feng, J. H. Kwak, X. Wang and J.-X. Zhou, Tetravalent half-arc-transitive graphs of order 2pq, J. Algebraic Combin. 33 (2011), 543-553, doi:10.1007/s10801-010-0257-1.
[12]	C. D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981), 243-256, doi:10.1007/bf02579330.
[13]	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.
[14]	B. Huppert, Endliche Gruppen. I, Die Grundlehren der Mathematischen Wissenschaften, Band 134, Springer-Verlag, Berlin-New York, 1967, doi:10.1007/978-3-642-64981-3.
[15]	K. Kutnar, D. Marusic and P. Sparl, An infinite family of half-arc-transitive graphs with universal reachability relation, European J. Combin. 31 (2010), 1725-1734, doi:10.1016/j.ejc.2010. 03.006.
Y. Wang and Y.-Q. Feng: Half-arc-transitive graphs of prime-cube order of small valencies 109
[16]	K. Kutnar, D. Marusic, P. Sparl, R.-J. Wang and M.-Y. Xu, Classification of half-arc-transitive graphs of order 4p, European J. Combin. 34 (2013), 1158-1176, doi:10.1016/j.ejc.2013.04. 004.
[17]	C. H. Li, On isomorphisms of connected Cayley graphs, Discrete Math. 178 (1998), 109-122, doi:10.1016/s0012-365x(97)81821-3.
[18]	C. H. Li and H.-S. Sim, On half-transitive metacirculant graphs of prime-power order, J. Combin. Theory Ser. B 81 (2001), 45-57, doi:10.1006/jctb.2000.1992.
[19]	D. Marusic, Vertex transitive graphs and digraphs of order pk, in: Cycles in graphs (Burnaby, B.C., 1982), North-Holland, Amsterdam, volume 115 of North-Holland Math. Stud., pp. 115128, 1985, doi:10.1016/s0304-0208(08)73001-9.
[20]	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.
[21]	D. Marusic, Quartic half-arc-transitive graphs with large vertex stabilizers, Discrete Math. 299 (2005), 180-193, doi:10.1016/j.disc.2004.02.025.
[22]	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.
[23]	P. Potocnik, P. Spiga and G. Verret, A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two, Ars Math. Contemp. 8 (2015), 133-148, http: //amc-journal.eu/index.php/amc/article/view/55 9.
[24]	D. J. S. Robinson, A Course in the Theory of Groups, volume 80 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2nd edition, 1996, doi:10.1007/978-1-4419-8594-1.
[25]	P. Spiga, Constructing half-arc-transitive graphs of valency four with prescribed vertex stabilizers, Graphs Combin. 32 (2016), 2135-2144, doi:10.1007/s00373-016-1678-y.
[26]	W. T. Tutte, Connectivity in Graphs, Mathematical Expositions, No. 15, University of Toronto Press, Toronto, Ont.; Oxford University Press, London, 1966.
[27]	P. Sparl, A classification of tightly attached half-arc-transitive graphs of valency 4, J. Combin. Theory Ser. B 98 (2008), 1076-1108, doi:10.1016/j.jctb.2008.01.001.
[28]	P. Sparl, On the classification of quartic half-arc-transitive metacirculants, Discrete Math. 309
(2009),	2271-2283, doi:10.1016/j.disc.2008.05.006.
[29]	Y. Wang and Y.-Q. Feng, Half-arc-transitive graphs of prime-cube order of small valencies, 2016, arXiv:1605.08123 [math.CO].
[30]	Y. Wang, Y.-Q. Feng and J.-X. Zhou, Cayley digraphs of 2-genetic groups of odd prime-power order, J. Combin. Theory Ser. A 143 (2016), 88-106, doi:10.1016/j.jcta.2016.05.001.
[31]	M.-Y. Xu, Half-transitive graphs of prime-cube order, J. Algebraic Combin. 1 (1992), 275-282, doi:10.1023/a:1022440002282.
[32]	M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182 (1998), 309-319, doi:10.1016/s0012-365x(97)00152-0.
[33]	J.-X. Zhou, Tetravalent half-arc-transitive p-graphs, J. Algebraic Combin. 44 (2016), 947-971, doi:10.1007/s10801-016-0696-4.