ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 9 (2015) 1-18 4-valent graphs of order 6p2 admitting a group of automorphisms acting regularly on arcs Mohsen Ghasemi Department of Mathematics, Urmia University, Urmia 57135, Iran Pablo Spiga Dipartimento di Matematica e Applicazioni, University ofMilano-Bicocca, Via Cozzi 55, 20125 Milano, Italy Received 9 May 2012, accepted 5 February 2014, published online 7 May 2014 In this paper we classify the 4-valent graphs having 6p2 vertices, with p a prime, admitting a group of automorphisms acting regularly on arcs. As a corollary, we obtain the 4-valent one-regular graphs having 6p2 vertices. Keywords: One-regular graphs, 4-valent, Cayley graphs. Math. Subj. Class.: 20B25, 05C25 1 Introduction For a finite, simple and undirected graph X, we use V(X), A(X) and Aut(X) to denote its vertex set, arc set and automorphism group, respectively. The graph X is said to be B-vertex-transitive, respectively B-arc-transitive, if B is a subgroup of Aut(X) acting transitively on V(X), respectively A(X). When B = Aut(X), the prefix B in the above notation is omitted. Moreover, X is said to be one-regular if Aut(X) acts regularly on A(X), that is, X is arc-transitive and | Aut(X)| = |A(X)|. Obviously, one-regular graphs are connected, and a graph of valency 2 is one-regular if and only if it is a cycle. The first example of a 3-valent one-regular graph was constructed by Frucht [10], with 432 vertices. Later on, a considerable amount of work has been done on 3-valent one-regular graphs as part of the more general problem dealing with the classification of the 3-valent arc-transitive graphs (see [5, 6, 7, 8, 19, 30]). Marusic and Pisanski [17] have fully classified the 3-valent one-regular Cayley graphs on a dihedral group, and Kwak et al. [14] have similarly classified those of valency 5. Moreover, more E-mail addresses: m.ghasemi@urmia.ac.ir (Mohsen Ghasemi), pablo.spiga@unimib.it (Pablo Spiga) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ Abstract 2 Ars Math. Contemp. 9 (2015) 93-107 recently, Feng and Li [9] have classified one-regular graphs of square-free order and of prime valency. Tetravalent one-regular graphs have also received considerable attention (see [1, 2, 15, 16, 24, 25, 28, 29]). In this paper we are concerned with the classification of the 4-valent one-regular graphs. We recall that such graphs are already classified when their orders are a prime or the product of two (not necessarily distinct) primes [3,21,22,26,29,28]. Moreover, for p and q primes, the classification of the 4-valent one-regular graphs of order 4p2 or 2pq is given in [4, 31]. In this context we prove the following. Theorem 1.1. Let p be a prime and let X be a 4-valent graph of order 6p2 admitting a group of automorphisms acting regularly on A(X ). Then one of the following holds: (i) X is isomorphic to C(2;3p2,1), C±1(p;6, 2), Yp,±i, YZp±v-Î or Zp±v=3 (see Section 3 for the definition of these graphs); (ii) X is a Cayley graph over G with connection set S where (a) G = (x,y | xp = y6p = [x, y] = 1} and S = {y, y-1,xy, (xy)-1}, or (b) G = (x,y,z | xp = y3p = z2 = [x, y] = [x,z] = 1,yz = y-1} and S = {xz,x-1z,xeyz,x-eyz} (here e2 = —1 (mod p) andp = 1 (mod 4)), or (c) G = (x,y,z | xp = y3 = z2 = [x,y] = [x, z] = 1,yz = y-1} and S = {xz, x-1z, xyz, x-1yz}, or (d) G = (x,y,z | xp = y3 = z2 = [x,y] = [x, z] = 1,yz = y-1} and S = {xz, x-1z, xeyz, x-eyz} (here e2 = —1 (mod p2)), or (e) G = (x, y,z,t | xp = yp = z3 = t2 = [x, y] = [x, z] = [x, t] = [y, z] = [y, t] = 1, zl = z-1} and S = {xt, x-1t, yzt, y-1zt}; (iii) p G {2, 3, 5} and X is described in Section 6. The definition of the graphs in part (i) requires a fair amount of notation and terminology, so we do not include their description in this introductory section. Observe that if p < 7, then ^(X)| = 24, 54, 150 or 294. Since a complete census of the 4-valent arc-transitive graphs of order at most 640 has been recently obtained by Potocnik, Spiga and Verret [18, 19], for p G {2, 3, 5,7}, the 4-valent graphs of order 6p2 admitting a group of automorphisms acting regularly on A(X) can be downloaded (in magma format) from [18]. The proof of Theorem 1.1 is based on "normal quotient" techniques. This method is very powerful and allows to obtain results like Theorem 1.1 when the order of the graph has a prime factorization that is not too complicated (the multiplicity and the number of prime factors are both small). However there are two natural limits to this technique. First, as the order of the graph X becomes more complicated, the local properties of the quotient graph XN might not be strong enough to be lifted to the graph X we start with (to see a concrete example of this situation see "Case XP = O" in the proof of Theorem 1.1). Second, we believe that results like Theorem 1.1 are useful only when the list of graphs is not too long or too cumbersome to use. Therefore, although some of our arguments apply to graphs having order more complicated than 6p2 we do not pursue this classification here because of the natural complications describing each possible family. A direct application of Theorem 1.1 gives the following. Corollary 1.2. Let p be a prime and let X be a 4-valent one-regular graph X of order 6p2. Then one of the following holds: M. Ghasemi and P. Spiga: 4-valent graphs of order 6 p2 admitting. 3 (i) X is isomorphic to Yp±\, Yp ±^3, Zp,±y—■ or Zp,±y-3 (see Section 3 for the defini- tion of these graphs); (ii) X is a Cayley graph over G with connection set S where (a) G = (x,y | xp = y6p = [x, y] = 1} and S = {y, y-1,xy, (xy)-1}, or (b) G = (x,y,z | xp = y3p = z2 = [x,y] = [x,z] = 1,yz = y-1} and S = {xz,x-1z,xeyz,x-eyz} (here e2 = —1 (mod p) andp = 1 (mod 4)), or (c) G = (x,y,z | xp = y3 = z2 = [x, y] = [x, z] = 1,yz = y-1} and {xz, x-1z, xyz, x-1yz}, or (d) G = (x,y,z | xp2 = y3 = z2 = [x, y] = [x, z] = 1,yz = y-1} and {xz,x-1z,xeyz,x-eyz} (here e2 = —1 (mod p2)); (iii) p G {2,3, 5} and X is described in Section 6. Observe that we are not claiming that every graph in Corollary 1.2 is one-regular. The structure of the paper is elementary: in Section 2 we introduce the notation and some basic results that we will need for our proof of Theorem 1.1. Then in Sections 3 and 4 we present some graphs revelant to our investigation. In Section 5 we prove Theorem 1.1 and Corollary 1.2. In Section 6 we give the graphs in part (iii) of Theorem 1.1, and in part (iii) of Corollary 1.2. Acknowledgements. A toast to our friend Primoz Potocnik for being constructively critical. 2 Preliminaries In this section, we introduce some notations and definitions as well as some preliminary results which will be used later in the paper. Let X be a connected vertex-transitive graph, and let B < Aut(X) be vertex-transitive on X. Suppose that there is some group N such that 1 = N < B, and N is intransitive in its action on V(X). The normal quotient XN is the graph whose vertices are the orbits of N on V(X), with an edge between two distinct vertices vN and wN in V(XN), if and only if there is an edge of X between v0 and w0, for some v0 G vN and some w0 G wN. Normal quotients were introduced by Praeger in [20] and they turned out to be an invaluable tool for the classification of certain families of vertex-transitive graphs. In fact, our proof of Theorem 1.1 heavily relies on normal quotient techniques. For a positive integer n, we denote by Zn the cyclic group of order n as well as the ring of integers modulo n, by Z*n the invertible elements of Zn, by D2n the dihedral group of order 2n, and by Cn and Kn the cycle and the complete graph of order n, respectively. For a group G and a subset S of G with 1 G S and S = S-1, the Cayley graph Cay(G, S) on G with connection set S is defined to have vertex set G and edge set {{g,sg} | g G G, s G S}. For the benefit of the reader, we report here [12, Theorems 1.1 and 1.2] and [11, Theorem 1.1], respectively. Theorem 2.1 ([12, Theorem 1.1]). Let X be a connected B-arc-transitive 4-valent graph, and let N be a minimal normal p-subgroup of B with orbits on V(X) of size ps. Let K denote the kernel of the action of B on N orbits and let a be a vertex of X. If the quotient XN is a cycle of length r > 3, then one of the following holds: 4 Ars Math. Contemp. 9 (2015) 93-107 (a) p = 2 and X = C(2; r,s); (b) p is odd and, if \Ka\ = 2s, then X = C±1(p; st, s) or X = C±e(p; 2st, s) for some t > 1. Theorem 2.2 ([12, Theorem 1.2]). Let X be a connected B-arc-transitive 4-valent graph, and let N = Zp (p an odd prime) be a minimal normal subgroup of B with orbits on V (X) of size ps. Let K denote the kernel of the action of B on N-orbits and let a be a vertex of X. If the quotient XN is a cycle of length r > 3, then one of the following holds: (a) s = 1 or 2, Ka = Z2 and X = C±1(p; st, s) or X = C±E(p; 2st, s) for some t > 1; (b) s = 2, Ka = Z2 and X = C±1(p;2t, 2), or X belongs to one of two families described in [12, Lemmas 8.4 and 8.7]. (The graphs C(2; r, s), C±1(p; st, s), C±E(p; 2st, s) and the graphs in [12, Lemma 8.4 and 8.7] are define in Section 3.) Theorem 2.3 ([11, Theorem 1.1]). Let X be a connected 4-valent B-arc-transitive graph. For each normal subgroup N of B, one of the following holds: (a) N is transitive on V(X); (b) X is bipartite and N acts transitively on each part of the bipartition; (c) N has r > 3 orbits on V(X), the quotient graph XN is a cycle of length r, and B induces the full automorphism group D2r on XN; (d) N has r > 5 orbits on V(X), N acts semiregularly on V(X), the quotient graph XN is a connected 4-valent B/N-symmetric graph, and X is a B-normal cover of XN. 3 Some families of graphs In this section we present some of the graphs relevant to Theorem 1.1 and Corollary 1.2. All of these graphs were introduced in the pivotal paper [12] of Gardiner and Praeger. (Here we do not include the description of all the graphs in [12], but only those that are closely related to our investigation.) 3.1 The graphs C(2; r, 1) The graph C(2; r, 1) is the lexicographic product of a cycle of length r and an edgeless graph on 2 vertices. In other words, V(C(2; r, 1)) = Z2 x Zr with (u, i) being adjacent to (v,j) if and only if i - j e {-1,1}. From [12, Definition 2.1], it follows that C(2; r, 1) is not one-regular. 3.2 The graphs C±1(p; st, s) (We will be only interested to the case s e {1,2}.) The graph C±1(p; st, s) has vertex set Zp x Zst. To describe the adjacencies write every vertex of C±1(p; st, s) as v = ((xo,. .., Xi-1, Xi, Xi+1, .. ., Xs- 1),ms + i), with x0,..., xs-1 e Zs, 0 < i < s and 0 < m 5, we have Aut(Yp,u) = Bu. Next we define Yp ±^3. Suppose p > 5 and let u e Zp be a square root of 3 (mod p). (Observe that, from the law of quadratic reciprocity, for this example to exist we need p = ±1 mod 12.) Let N = (a0, a1) be an elementary abelian p-group of order p2 and let K be the group with presentation K = (a, t, w | a12 = t2 = w2 = [a, w] = [t, w] = 1, a6 = = a-1). Clearly, K = (a, t) = D24. We let K act on N via a1 1 a1 ao ao aW Set Bu = N xK and = (w, t). As for Yp,±1, the graph Yp,u is defined by Cos (Bu, Hu, a-1a0). From Proposition 3.1, it follows that Yp,u is a Bu-arc-transitive graph of valency 4 with 6p2 vertices and Bu acts regularly on A(Yp,u). Moreover, from [12, Section 8], we have = and Aut(Yp,„) = B„. 3.5 The graphs arising from [12, Lemma 8.7]: 3 and Zp,±^=T As for Section 3.4, the graphs described in [12, Section 8 and Lemma 8.7] are very general, here we present only the graphs relevant to the scope of this article. We start by defining Z ±^3. Suppose p > 5 and let u e Zp be a square root of -3 (mod p). (Observe that, from the law of quadratic reciprocity, for this example to exist we need p = 1 mod 6.) Let N = (a0, a1) be an elementary abelian p-group of order p2 and let K be the group with presentation K = (a, t, w | a6 = t4 [a, w] = [t, w] = 1, t2 T 2-1 w, a = Ta ). We let K act on N via a1 aoa1 a a1 -1 o 1 Set Bu = N x K and Hu = (t). Now the graph Zp,u is defined by Cos(Bu, Hu, a-1a0). From Proposition 3.1, it follows that Zp,u is a Bu-arc-transitive graph of valency 4 with 6p2 vertices and Bu acts regularly on A(Zp,u). Moreover, from [12, Section 8], we have and Aut(Zp,„) G a= a 0 G W a a =a a 1 1 1 w, a 1 aT = W a a 0 1 aG = u aT = a 1 1 1 2 w G T W a= a= a 0 0 1 W a= a a =a 1 1 M. Ghasemi and P. Spiga: 4-valent graphs of order 6 p2 admitting. 7 Finally, we define Z Suppose p > 5 and let u G Zp be a square root of -1 (mod p). (Observe that, from the law of quadratic reciprocity, for this example to exist we need p = 1 mod 4.) Let N = (a0, a^ be an elementary abelian p-group of order p2 and let K be the group with presentation K = (a, t, w | a12 = t4 = w2 = [a, w] = [t, w] = 1, a6 = t2 = w, aT = a-1}. We let K act on N via ag" = ai aj = ai aW = a-1 ag = aoa" , ai = a-1 , aW = a-1 . Set Bu = N x K and Hu = (t}. As for Z ±^33, the graph Zp,u is defined by Cos(Bu, Hu, a-1a0). From Proposition 3.1, it follows that Zp,u is a Bu-arc-transitive graph of valency 4 with 6p2 vertices and Bu acts regularly on A(Zp,u). Moreover, from [12, Section 8], we have Z = and Aut(Zp,u) = Bu. 4 Graphs for Theorem 1.1 (ii) In this section we describe the examples introduced in Theorem 1.1 (ii) (and their relation to the graphs in Section 3). For simplicity here we assume thatp > 5. The graphs described in Sections 4.1 and 4.6 were already introduced with much more information and details in [28], here we include yet again their construction for making our note self-contained. 4.1 4-Valent normal Cayley graphs over Zp X Z6p with p > 5 prime We describe the connected normal 4-valent arc-transitive Cayley graphs over the group Zp X Z6p. Let p be a prime and let G be the group given by generators and relations G = (x,y | xp = y6p = [x,y] = 1}. Let S be a subset of G and assume that X = Cay(G, S) is connected, normal, 4-valent and arc-transitive. Since X is normal and arc-transitive and since G is abelian of exponent 6p, we see that S consists of elements of order 6p. Denote by S6p the elements of G of order 6p. Therefore S ÇS6p = {x°y6 | a G Zp,b G Z*p}. It is clear that Aut(G) acts transitively on S6p by conjugation. In particular, replacing 5 by a suitable Aut(G)-conjugate, we may assume that y G S. Therefore S = {y,y ,xu yv }, for some u G Z* and for some v G Z6p. Let B = {^ G Aut(G) | yv = y}. Given ^ G B, we have : fx ^ x°y66 ^ ' 1 y ^ y with a, b G Zp and a = 0. Note that every invertible element of Z6p is of the form 1 + 6b or —1 + 6b, for some b G Zp. Therefore, we may choose a, b G Zp with (xy)v = x"yv or 8 Ars Math. Contemp. 9 (2015) 93-107 (xy 1)v = xuyv. Thus, replacing S by a suitable B-conjugate, we may assume that either xy G S or xy-1 G S, that is, Let ^ be the automorphism of G with xv = x and yv = y 1. Clearly, ^ maps the first possibility for S onto the second. Therefore, we may assume that The graph X is in Theorem 1.1 (ii) (a). Also, using [12, Definition 2.2], we see that X is isomorphic to G±x(p; 6p, 1). 4.2 4-Valent normal Cayley graphs over Zp x D6p with p > 5 prime We describe the connected normal 4-valent arc-transitive Cayley graphs over the group Zp X D6p. Let p be a prime and let G be the group given by generators and relations Let S be a subset of G and assume that X = Cay(G, S) is connected, normal, 4-valent and arc-transitive. Since X is normal and arc-transitive, every element of S has the same order. The elements of G of odd order lie in (x, y) and the involutions of G lie in (y, z). Since X is connected, G = (S) and hence S consists of elements of order 2p. Denote by S2p the elements of G of order 2p. Therefore s ç S2p = {xVz | b g Z3p, a g z;}. We now consider the action of the automorphism group Aut(G) of G on S2p. Let ^ G Aut(G). Clearly, ^ is uniquely determined by the images of x, y and z. By considering the element orders of G, we need to have Since [x, z] = 1, the element xv needs to commute with zv and so, with a direct computation, we see that 3b = 0. Also, as yz = y-1, we have (yv)z^ = (yv)-1, but this happens only for c = 0. Summing up, This shows that all elements of S2p are Aut(G)-conjugate to xz. Therefore, replacing S by a suitable conjugate under Aut(G), we may assume that xz G S. In particular, S = {xz, x-1z, xuyvz, x-uyvz}, for some u, v. As G = (S} < (x, z, yv}, we have that S = {y, y 1, xy, x ly x}, or S = {y, y-1, xy-1, x-1y}. S = {y,y 1, xy, x 1y 1}. G = (x, y, z | xp = y3p = z2 = [x, y] = [x, z] = 1, yz = y 1). x ^ x°y36 c d y ^ xcyd z ^ yez. (4.1) M. Ghasemi and P. Spiga: 4-valent graphs of order 6 p2 admitting. 9 Let B = {<£> € Aut(G) | (xz)v = xz}. From (4.1), we see that ^ G B only if x^ = x and z^ = z. In particular, replacing S by a suitable B-conjugate, we may assume that x"yz G S, that is, v = 1. Thus S = {xz, x-1z, xuyz, x-uyz}. Let ^ G Aut(G) with Sv = S and (xz)v = x"yz (recall that such an automorphism exists because X is a normal arc-transitive Cayley graph over G). From (4.1), we have xv = xu, zv = yz and yv = yd (for some d coprime to 3p). Now, (x"yz)v = xu yd+1 z G S. If xu yd+1z G {x"yz, x-uyz}, then d = 0, contradicting the fact that d is coprime to 3p. Therefore xu yd+1z G {xz, x-1z} and u2 = ±1. Thus we have one of the following two possibilities for S: S = {xz, x-1z, xyz, x-1yz}, or S = {xz, x-1z, xeyz, x-eyz}, where e2 = —1 (note that in the second case p = 1 (mod 4)). Now we focus our attention to the first possibility for S. Take {x ^ x y ^ y-1 z ^ yz. Since ^ fixes set-wise S, we have G x < Aut(X). We see that (z-0)2 = z^z^ = z(^z^) = zz^ = zyz = yz = y-1 and so z-0 has order 6p. Moreover = (xz= x^ = x and x commutes with z-0. Therefore (x, z^} = Zp x Z6p. It is immediate to see that (x, z^} acts regularly on the vertices of X and so X is a Cayley graph over Zp x Z6p. In particular, from the discussion in Section 4.1 (or with a direct computation) we obtain that X is isomorphic to the graph in Theorem 1.1 (ii) (a). Therefore we may assume that p = 1 (mod 4) and that S = {xz, x-1z, xeyz, x-eyz} where e2 = —1. The graph X is in Theorem 1.1 (ii) (b). Also, using [12, Definition 2.3] (or Section 3.3), we see that X is isomorphic to C±e(p; 6p, 1). 4.3 4-Valent normal Cayley graphs over Zp x Zp x Dq with p ^ 5 prime We proceed as in the previous two examples. Let p be a prime and let G be the group given by generators and relations G = (x, y, z, t | xp = yp = z3 = t2 = [x, y] = [x, z] = [x, t] = [y, z] = [y, t] = 1, z4 = z-1}. Let S be a subset of G and assume that X = Cay(G, S) is connected, normal, 4-valent and arc-transitive. As the elements of G of odd order lie in (x, y, z} and the involutions of G lie in (z, t}, we must have that S consists of elements of order 2p. Since (x, y} and (z, t} are characteristic subgroups of G, we have Aut(G) = Aut((x,y}) x Aut((z,t}) = GL2 (p) x D6. It follows easily from this description of Aut(G) and the connectivity of X that we may assume that S = {xt, x-1t, yzt, y-1zt}. Thus we obtain the graphs in Theorem 1.1 (ii) (e). 10 Ars Math. Contemp. 9 (2015) 93-107 We show that X is not one-regular and hence it is not relevant for Corollary 1.2. Take ^ : x ^ x 1 y ^ y z ^ z t ^ t. Clearly, ^ defines an automorphism of G that fixes set-wise S. Since ^ fixes the neighbour yzt of 1 and maps xt to x-1t, we see that Aut(X) is not regular on A(X). 4.4 4-Valent normal Cayley graphs over Z3p x D2p with p ^ 5 prime Let G be the group given by generators and relations G = (x, y, z | x3p = yp = z2 = [x,y] = [x, z] = 1,yz = y-1). Let S be a subset of G and assume that X = Cay(G, S) is connected, normal, 4-valent and arc-transitive. As the elements of G of odd order lie in (x, y), the involutions of G lie in (y, z) and the elements of order 2p lie in (x3, y, z), we must have that S consists of elements of order 6p. Denote by S6p the elements of G of order 6p. Therefore S C Sep = {xay6z | a e Z3p, b e Zp}. Arguing as in the previous examples, we see that Aut(G) acts transitively on S6p and hence we may assume that xz e S. In particular, S = {xz, x-1z, xuyvz, x-uyvz}, for some u e Zgp and some v e Zp. Let B = {^ e Aut(G) | (xz)v = xz}. Clearly, if (xz)v = xz, then xv = x and zv = z because z = (xz)3p and x2 = (xz)2. Using this observation, it is easy to see that the elements ^ e B are of the form ^ : < y ^ x3ay6 for some a, b e Zp with b = 0. Therefore, we may choose a and b with (x"yvz)v = xyz or (x"yvz)v = x-1yz. Therefore (as usual), replacing S by a suitable B-conjugate, we may assume that S = {xz, x-1z, xyz, x-1yz}. Take {x ^ x y ^ y-1 z ^ yz. Clearly, ^ defines an automorphism of G. Since ^ fixes set-wise S, we have G x < Aut(X). We see that x x z z (z-0)2 = z^z^ = z(^z^) = zz^ = zyz = yz = y 1 M. Ghasemi and P. Spiga: 4-valent graphs of order 6 p2 admitting. 11 and so z^ has order 2p. Moreover = (xz= x^ = x and x commutes with z^. Therefore (x, z^} = Z3p x Z2p = Zp x Z6p. It is immediate to see that (x, z^} acts regularly on the vertices of X and so X is a Cayley graph over Zp x Z6p. In particular, from the discussion in Section 4.1 (or with a direct computation) we obtain that X is isomorphic to the graph in Theorem 1.1 (ii) (a). 4.5 4-Valent normal Cayley graphs over Zp2 x D6 with p > 5 prime Let G be the group given by generators and relations G = (x,y, z | xp = y3 = z2 = [x, y] = [x, z] = 1,yz = y-1}. Let S be a subset of G and assume that X = Cay(G, S) is connected, normal, 4-valent and arc-transitive. A moment's thought gives that S consists of elements of order 2p2. Denote by S2p2 the elements of G of order 2p2. Therefore S Ç S2P2 = {xay6z | a G Zp2, b G Z3}. Since (x} and (y, z} are characteristic subgroups of G, we have Aut(G) = Aut((x}) x Aut((y, z}) = Z*2 x D6 and Aut(G) acts transitively on S2p2. Hence we may assume that xz G S. In particular, S = {xz, x-1z, x"yvz, x-uyvz}, for some u G Zp2 and some v g Z3. Replacing S by a suitable Aut(G)-conjugate, we may assume that v = 1, that is, S = {xz, x-1z, x"yz, x-uyz}. Let ^ G Aut(G) with Sv = S and (xz)v = x"yz (recall that such an automorphism exists because X is a normal arc-transitive Cayley graph over G). From the description of Aut(G), we have xv = xu and zv = yz and yv = yd (for some d G Z3). Now, (x"yz)v = xu yd+1z G S. As d = 0, we obtain d = —1 and u2 = ±1. Thus we have one of the following two possibilities for S: S = {xz, x-1z, xyz, x-1yz}, or S = {xz, x-1z, xeyz, x-eyz}, where e2 = —1 (note that in the second case p = 1 (mod 4)). In particular, we obtain that X is isomorphic to the graph in Theorem 1.1 (ii) (c) or (d). 4.6 4-Valent normal Cayley graphs over Zp2 x Z6 with p > 5 This case is by far the easiest to deal with and we leave it to the conscious reader. There is only one graph arising, namely the graph in Theorem 1.1 (ii) (c). 5 Proof of Theorem 1.1 and Corollary 1.2 We start with some technical preliminary lemmas that will be useful in the proof of Theorem 1.1. Lemma 5.1. Let p be a prime with p > 5 and let N be a normal subgroup of G with |N| = p and G/N = Zp x Z6 or G/N = Zp x D6. Then G is isomorphic to one of the following groups 12 Ars Math. Contemp. 9 (2015) 93-107 (i) Zp2 x Ze or Zp2 x De; or (ii) Zp x (Zp x Z6) or Zp x (Zp x De). Proof. Let P be a Sylow p-subgroup of G. Since G is soluble, G contains a subgroup Q with |Q| = 6. As g/n = Zp x Ze or G/N = Zp x De, we have that QN/N = Q (that is, Q = Ze or Q = De) and that Q centralizes P/N. If P is cyclic, then Q centralizes P by [13, Theorem 1.4]. So G = P x Q and part (i) follows. Suppose that P is an elementary abelian p-group. The action of Q by conjugation on P endows P of a structure of an ZpQ-module. As Q has order coprime to p, the ZpQ-module N is completely reducible, that is, P = N x N', for some normal subgroup N' of G of size p. As Q centralizes P/N, we see that Q centralizes N'. Thus G = N' x (N x Q) and part (ii) follows. □ Lemma 5.2. Let p be a prime with p > 7 and let X be a connected normal 4-valent arc-transitive Cayley graph over one of the groups G in Lemma 5.1 (ii). Let P be a Sylow p-subgroup of G. Assume that P < G and that Xp = C6. Then either G = Zp x Zep, or G = Z3p x D2p, or G = Zp x Dep, or G = Zp x Zp x De. Proof. From Lemma 5.1 (ii), we have G = (x) x ((y) x (z, t)) with (x, y) = Zp x Zp, |z| = 3 and |t| = 2. Moreover, [z, t] = 1 if G = Zp x (Zp x Ze) and z4 = z-1 if G = Zp x (Zp x De). If z centralizes y, then G = (x) x ((yz) x (t)). In particular, G = Zp x Z6p if t centralizes both y and z, G = Zp x Dep if t inverts both y and z, G = Z3p x D2p if t centralizes z and inverts y, and G = Zp x Zp x De if t inverts z and centralizes y. In remains to consider the case that z does not centralize y. We show that this case actually does not arise (here we use the fact that G admits a normal Cayley graph). Note that the automorphism group of Zp is cyclic and hence De cannot act faithfully as a group of automorphisms on Zp. Since we are assuming that z does not centralize y, we must have that G = Zp x (Zp x Ze), that is, [z, t] = 1. Let S be a subset of G with X = Cay(G, S). Write A = Aut(X). Since (x) is a characteristic subgroup of G and since G < A, we obtain that (x) < A and Y = X(x) is a normal quotient having 6p vertices. In particular, Y has valency 2 or 4. Let K be the kernel of the action of A on V(Y) and assume that Y is a cycle. In particular, A/K = D12p. Now D12p contains exactly two regular subgroups, one isomorphic to Zep and the other to Dep. Therefore GK G G "K = GnK = (x) = (y) x (z,t) is isomorphic either to Zep or to Dep, contradicting the fact that z does not centralize y. Thus Y is a 4-valent Cayley graph over GK/K = (y) x (z, t) and K = (x). Now, P/K has order p and is therefore a minimal normal subgroup of A/K. Also, Yp/k = XP = Ce and so we are in the position to apply Theorem 2.1 (b) to A/K, P/K and Y. Hence Y = G±1(p; 6,1) or Y = C±e(p; 6,1). From Sections 3.2 and 3.3 we see that Y is a Cayley graph over Zp x Ze or over Zp x De. However, (y) x (z, t) is isomorphic to neither of these groups, a contradiction. □ In what follows we denote by O the graph Ke - 6K2, that is, Ke with a perfect matching removed. Clearly, O is connected, 4-valent and |V(O)| = 6. We refer to O as the Octahedral graph. M. Ghasemi and P. Spiga: 4-valent graphs of order 6 p2 admitting. 13 Proof of Theorem 1.1. We first consider the case that p > 11. Let B be a subgroup of Aut(X) acting regularly on A(X), let Bv be the stabilizer in B of the vertex v e V(X) and let P be a Sylow p-subgroup of B. We show that P is normal in B. Since |B| = |A(X)| = 24p2, Sylow's theorems show that the number of Sylow p-subgroups of B is equal to |B : NB (P)| = 1 + kp, for some k > 0. If k = 0, then P is normal in B and thus we may assume that k > 1. Now, 1 + kp divides 24 and this is possible if and only if k =1 and p = 23, or k = 1 and p = 11. Suppose that k = 1 and p = 23. Now |B : NB (P)| = 24. So NB (P) = P and CB (P) = NB (P). Therefore, by the Burnside's p-complement theorem [27, page 76], we see that B has a normal subgroup N of order 24. In particular, P acts by conjugation as a group of automorphisms on N. As a group of order 24 does not admit non-trivial automorphisms of order 23, we see that P centralizes B. Thus B = N x P and P is normal in B. Finally, suppose that k =1 and p =11. Now, |B : Nb(P)| = 12. Consider the permutation group B induced by the action of B on the cosets of NB (P). Now, B has degree 12 and has order divisible by 11 because (by hypothesis) P is not normal in B. Therefore B is a 2-transitive group whose order divides 24 • 112. A quick inspection on the list of 2-transitive groups of degree 12 in magma shows that this is impossible. This final contradiction gives that P is normal in B. As usual, we denote by XP the normal quotient of X via P. The rest of the proof is a case-by-case analysis depending upon the structure of the normal quotient XP .At the end of the proof of each case we use the symbol ■ to mean that the theorem is proved in the case under consideration. As |Bv | =4, we have Bv n P =1 and P acts semiregularly on V(X). Thus the orbits of P on V(X) have size p2 and |V(XP)| = 6. In particular, XP is either the cycle C6 or the octahedral graph O (depending on whether XP has valency 2 or 4). Case A: XP = O. Fix v a vertex of X and let K be the kernel of the action of B on V (XP). As XP has valency 4, we obtain |B/K| = 24 and K = P. Now, the automorphism group W of O is isomorphic to the wreath product Z2 I Sym(3), which has order 48. Therefore B/P is isomorphic to a subgroup of index 2 in W. Labelling the vertices of O as {1, 2, 3,4,5,6} (so that {{1,2}, {3,4}, {5, 6}} is the system of imprimitivity for W), we may assume that W = ((1, 2), (3, 4), (5, 6), (1, 3)(2,4), (1, 5)(2, 6)). The group W has exactly three subgroups of index 2. Namely, Wi = ((1, 2)(3,4), (1, 2)(5, 6), (1, 3)(2,4), (1, 5)(2, 6)), W2 = ((1, 2), (3, 4), (5, 6), (1, 3, 5)(2, 4, 6)), W3 = ((1, 2)(3,4), (1, 2)(5, 6), (1, 3, 5)(2,4, 6), (1, 2)(3, 6)(4, 5)). The group B/P acts by conjugation as a group of automorphisms on P. So, if B/P = Wj, then Wj admits an action as a group of automorphisms on P. Assume that B/P acts faithfully on P, that is, CB (P) = P. In particular, Wj admits a faithful irreducible action on P. Suppose that P is cyclic. Then Aut(P) is cyclic and so B/P is cyclic. However, W1, W2 and W3 are not cyclic, a contradiction. Thus P is an elementary abelian p-group and Aut(P) = GL2(p) (the group of 2 x 2 invertible matrices). It is clear that the group SL2(p) has index 2 in GL2(p) and that SL2(p) contains a unique element of order 2. This shows that Wj has a normal subgroup T with Wj/T cyclic and with T containing at most 14 Ars Math. Contemp. 9 (2015) 93-107 one involution. A direct inspection on W^ W2 and W3 shows that such a normal subgroup T does not exist. Therefore B/P does not act faithfully on P and CB (P) > P. Another direct inspection on W1, W2 and W3 shows that W1 and W3 contain a unique minimal normal subgroup (namely, ((1,2)(3,4), (1,2)(5, 6)}, which has order 4) and W2 contains exactly two minimal normal subgroups (((1, 2)(3,4)(5,6)} having size 2 and ((1,2)(3,4), (1,2)(5, 6)} having size 4). Therefore, CB(P) contains a minimal normal subgroup Q with |Q| = 2 or |Q| = 4. Suppose that |Q| = 2 (and so B/P = W2). Now, W2/((1,2)(3,4)(5, 6)} = Alt(4) the alternating group on 4 letters. Arguing as in the previous paragraph, we see that Alt(4) cannot act faithfully on P. Therefore | CB (P) : P| > 4 and CB (P) contains a minimal normal subgroup R with |R| =4. So, replacing Q by R if necessary, we may assume that |Q| = 4. Since Q is characteristic in CB (P), we get that Q is normal in B. As 4 does not divide | V(X) |, we get that |Qv | = 2 and the Q-orbits have size 2. So, the quotient graph Xq is a cycle of length 3p2. Now from Theorem 2.1 (a), we obtain X = C(2; 3p2,1) and X is as in Theorem 1.1 (i). ■ For the remainder of the proof we may assume that XP = C6. Case B: P is a minimal normal subgroup of B. Fix v a vertex of X and let K be the kernel of the action of B on V(XP). As |B| = 24p2 and as XP has valency 2, we have B/K = D12 and |Kv| = 2. So, we see that Theorem 2.2 (b) applies (with s = 2), and X is isomorphic to C±1(p; 6, 2) or to one of the graphs defined in [12, Lemmas 8.4 and 8.7]. From Sections 3.2, 3.4 and 3.5, Theorem 1.1 (i) holds. ■ For the remainder of the proof we may assume that B has a minimal normal subgroup N with N < P and |N | = p. Now by Theorem 2.3 the normal quotient XN is either C6p or a 4-valent graph. Case C: Xn = C6p. Let K be the kernel of the action of B on V(XN). As |B| = 24p2 and XN is 2-valent, we have B/K = D12p and |Kv | = 2. So, we are in the position to apply Theorem 2.1 (b) (with s = 1) and thus X is isomorphic to either C±1(p; 6p, 1) or to C±e(p; 6p, 1). From Sections 4.1 and 4.2, we get that in the first case Theorem 1.1 part (ii) (a) holds and in the second case Theorem 1.1 part (ii) (b) holds. ■ For the remainder of the proof we may assume that XN is a 4-valent graph. So, X is a regular cover of XN. Denote by K the kernel of the action of B on V(XP) and recall that |K | = 2p2 because XP = C6. Also, note that the normal quotient (XN )P/N is isomorphic to XP. Now P/N is a minimal normal subgroup of B/N with orbits of size p. The kernel of the action of B/N on XP is K/N and |KvP/P| = 2. Therefore Theorem 2.1 (b) applies (with s = 1 and with B replaced by B/N), and so XN = C±1(p; 6,1) or XN = C±e(p; 6,1). From Sections 3.2 and 3.3, we see that C±1(p; 6,1) is anormal Cayley graph over Zp x Z6 and that C±e(p; 6,1) is a normal Cayley graph over Zp x D6. Let G/N be the normal subgroup of B/N acting regularly on V(XN), with G/N = Zp x Z6 or with G/N = Zp x D6. Clearly, G acts regularly on V(X) and thus X is a normal Cayley graph over G. From Lemma 5.1, we see that G is isomorphic either to Zp2 x Z6, or Zp2 x D6, or Zp x (Zp x Z6), or Zp x (Zp x D6). If G is isomorphic to Zp x (Zp x Z6), or Zp x (Zp x D6), then from Lemma 5.2 G is isomorphic to Zp x Z6p, or Zp x D6p, or Zp x Zp x D6, or Z3p x D2p. Now the proof follows from Sections 4.1, 4.2,4.3 and 4.4. M. Ghasemi and P. Spiga: 4-valent graphs of order 6 p2 admitting. 15 If G is isomorphic either to Zp2 x Z6 or Zp2 x D6, then the proof follows from Sections 4.5 and 4.6. It remains to consider the case that p < 7. When p = 7, we see from [18, 19] that there are seven 4-valent arc-transitive graphs on 6p2 vertices. A computer computation shows that six of these graphs are isomorphic to one of the graphs defined in Theorem 1.1 (i) and (ii), and the seventh does not admit a group of automorphisms acting regularly on arcs. When p = 5, we see from [18, 19] that there are ten 4-valent arc-transitive graphs on 6p2 vertices and they all admit a group of automorphisms acting regularly on arcs. It is a computer computation checking that eight of these graphs are isomorphic to one of the graphs defined in Theorem 1.1 (i) and (ii), and the remaining two are given in Section 6. When p = 3, we see from [18, 19] that there are five 4-valent arc-transitive graphs on 6p2 vertices and they all admit a group of automorphisms acting regularly on arcs. It is a computer computation checking that three of these graphs are isomorphic to one of the graphs defined in Theorem 1.1 (i) and (ii), and the remaining two are given in Section 6. When p = 2, the result follows again with a straightforward computation. □ Proof of Corollary 1.2. Observe that from Sections 3.1,3.2 and 4.3 the graphs C (2; 3p2,1), C±1 (p; 6, 2) and the graphs in Theorem 1.1 (ii) (e) are not one-regular. Now the result follows immediately from Theorem 1.1. □ 6 Description of the graphs in Theorem 1.1 part (iii) and Corollary 1.2 (iii) New now describe the exceptional graphs in Theorem 1.1 (iii) and Corollary 1.2 (iii). Case p = 2. (i) X = Cay((x), {x, x-1, x5, x-5}) where (x) is a cyclic group of order 24. Now, X is a normal one-regular Cayley graph. (ii) X = Cay((x), {x, x-1, x7, x-7}) where (x) is a cyclic group of order 24. Now, X is a normal one-regular Cayley graph. (iii) X = Cay(SL(2, 3), S) and with connection set Now, X is a normal one-regular Cayley graph. (v) X = Cay(G, S) with G = ((1,2,3), (1,2), (4, 5, 6,7)) = D x Z4 and S = {(1, 3)(4, 6)(5, 7), (1, 2, 3)(4, 5, 6, 7), (2, 3)(4, 6)(5, 7), (1, 3, 2)(4, 7, 6, 5)}. Now, X is neither a normal Cayley graph nor one-regular. Case p = 3. Now, X is a normal one-regular Cayley graph. (iv) X = Cay(SL(2, 3), S) and with connection set 16 Ars Math. Contemp. 9 (2015) 93-107 (i) X is the Cayley graph Cay(G, S), where G is the subgroup of GL(3, 3) generated by -10 0 0 1 0 0 0 1 1 1 0 010 001 100 0 1 1 0 0 1 and with connection set -1 -1 -1 0 1 -1 001 -1 -1 1 \ 0 1 1 I 0 0 1 J ( -1 1 1 \ (-1 1 -1 I 0 1 -1 I , I -0 11 V 0 0 1 0 01 Now, it is a computation to verify that X is not one-regular. (ii) X is the Cayley graph Cay(G, S), where G is the subgroup of GL(3,3) generated by -1 0 0 0 1 0 0 0 1 1 1 0 010 001 100 0 1 1 0 0 1 and with connection set -1 0 0 0 1 0 0 0 1 -1 1 0 0 1 0I , 0 1 ( -1 -1 \ ( -1 -1 0 I 0 1 -1 I , I -0 1 -1 V 0 0 1 0 01 Now, it is a computation to verify that X is one-regular. Case p = 5. (i) X is the coset graph Cos(G, H, g) where G = ((1, 2, 3,4, 5), (2, 5)(3,4), (6, 7, 8, 9,10), (8, 9,10)) = D5 x Alt(5), H = ((1,5)(2,4)(6,9)(8,10), (6,10)(8, 9)) and g = (1,3)(4,5)(6,10)(7, 8). Now, | Aut(X) | = 1200 and hence X is not one-regular. (ii) X is the coset graph Cos(G, H, g) where G = ((1, 2, 3,4, 5), (2, 5)(3,4), (6, 7, 8, 9,10), (8, 9,10)) = D5 x Alt(5), H = ((1, 5)(2,4)(7,10)(8,9), (7, 9)(8,10)) and g = (1, 2)(3,5)(6,7)(8, 9). Now, | Aut(X) | = 600 and hence X is one-regular. M. Ghasemi and P. Spiga: 4-valent graphs of order 6 p2 admitting. 17 References [1] K. Bercic and M. Ghasemi, Tetravalent arc-transitive graphs of order twice a product of two primes, Discrete Math. 312 (2012), 3643-3648. [2] C. Y. Chao, On the classification of symmetric graphs with a prime number of vertices, Trans. Amer. Math Soc. 158 (1971), 247-256. [3] Y. Cheng and J. Oxley, On weakly symmetric graphs of order twice a prime, J. Combin. Theory B 42 (1987), 196-211. [4] Y.-Q. Feng, K. Kutnar, D. Marusic and C. Zhang, Tetravalent graphs of order 4p2, accepted to Filomat. [5] Y.-Q. Feng and J. H. Kwak, Classifying cubic symmetric graphs of order 10p or 10p2, Science in China A 49 (2006), 300-319. [6] Y.-Q. Feng and J. H. Kwak, Cubic symmetric graphs of order twice an odd prime power, J. Austral. Math. Soc. 81 (2006), 153-164. [7] Y.-Q. Feng and J. H. Kwak, Cubic symmetric graphs of order a small number times a prime or a prime square, J. Combin. Theory B 97 (2007), 627-646. [8] Y.-Q. Feng, J. H. Kwak and K. S. Wang, Classifying cubic symmetric graphs of order 8p or 8p2, European J. Combin. 26 (2005), 1033-1052. [9] Y.-Q. Feng and Y-T. Li, One-regular graphs of square-free order of prime valency, European J. Combin. 32 (2011), 265-275. [10] R. Frucht, A one-regular graph of degree three, Canad. J. Math. 4 (1952), 240-247. [11] A. Gardiner and C. E. Praeger, On 4-valent symmetric graphs, European. J. Combin. 15 (1994) 375-381. [12] A. Gardiner and C. E. Praeger, A characterization of certain families of 4-valent symmetric graphs, European. J. Combin. 15 (1994), 383-397. [13] D. Gorenstein, Finite groups, Chelsea Publishing Company, New York, 1980. [14] J. H. Kwak, Y.S. Kwon and J. M. Oh, Infinitely many one-regular Cayley graphs on dihedral groups of any prescribed valency, J. Combin. Theory B. 98 (2008), 585-598. [15] J. H. Kwak and J. M. Oh, One-regular normal Cayley graphs on dihedral groups of valency 4 or 6 with cyclic vertex stabilizer, Acta Math. Sinica. English. Ser. 22 (2006), 1305-1320. [16] D. Marussics, A family of one-regular graphs of valency 4, European J. Combin. 18 (1997), 59-64. [17] D. Marusic and T. Pisanski, Symmetries of hexagonal graphs on the torus, Croat. ChemicaActa 73 (2000), 969-981. [18] P. Potocnik, P. Spiga and G. Verret, http://www.matapp.unimib.it/~spiga/census.html. [19] P. Potocnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, Jour. Symb. Comp. 50 (2013), 465-477. [20] C. E. Praeger, Imprimitive symmetric graphs, Ars Combin. 19 A (1985), 149-163. [21] C. E. Praeger, R. J. Wang and M. Y. Xu, Symmetric graphs of order a product of two distinct primes, J. Combin. Theory B 58 (1993), 299-318. [22] C. E. Praeger and M. Y. Xu, Vertex-primitive graphs of order a product of two distinct primes, J. Combin. Theory B 59 (1993), 216-245. [23] G. Sabidussi, Vertex-transitive graphs, Monatshefte Math. 68 (1961), 426-438. 18 Ars Math. Contemp. 9 (2015) 93-107 [24] C. Q. Wang and M. Y. Xu, Non-normal one-regular and 4-valent Cayley graphs of dihedral groups D2n, European J. Combin. 27 (2006), 750-766. [25] C. Q. Wang and Z. Y. Zhou, 4-valent one-regular normal Cayley graphs of dihedral groups, Acta Math. Sinica Chinese Ser. 49 (2006), 669-678. [26] R. J. Wang and M. Y. Xu, A classification of symmetric graphs of order 3p, J. Combin. Theory B 58 (1993), 197-216. [27] B. H. Wehrfritz, A second course on Group Theory, World Scientific, 1999. [28] J. Xu and M. Y. Xu, Arc-transitive Cayley graphs of valency at most four on Abelian groups, Southest Asian Bull. Math. 25 (2001), 355-363. [29] M. Y. Xu, A note on one-regular graphs, Chin. Sci. Bull. 45 (2000), 2160-2162. [30] J.-X. Zhou and Y.-Q. Feng, Cubic one-regular graphs of order twice a square-free integer, Sci. China Ser. A, Math 51 (2008), 1093-1100. [31] J.-X. Zhou and Y.-Q. Feng, Tetravalent one-regular graphs of order 2pq, J. Algebraic Combin. 29 (2009), 457-471.