ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 97-112
https://doi.org/10.26493/1855-3974.1327.6ee
(Also available at http://amc-journal.eu)
The arc-types of Cayley graphs
*
Marston D. E. Conder, Nemanja Poznanovic
Department of Mathematics, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand
Received 20 February 2017, accepted 6 November 2017, published online 26 February 2018
Let X be a finite vertex-transitive graph of valency d, and let A be the full automorphism group of X. Then the arc-type of X is defined in terms of the sizes of the orbits of the action of the stabiliser Av of a given vertex v on the set of arcs incident with v. Specifically, the arc-type is the partition of d as the sum n1 + n2 + ••• + nt + (m1 + m1 ) + (m2 + m2) + • • • + (ms + ms), where n1, n2,...,nt are the sizes of the self-paired orbits, and m1, m1, m2,m2,... ,ms,ms are the sizes of the non-self-paired orbits, in descending order.
In a recent paper, it was shown by Conder, Pisanski and Zitnik that with the exception of the partitions 1 + 1 and (1 + 1) for valency 2, every such partition occurs as the arc-type of some vertex-transitive graph. In this paper, we extend this to show that in fact every partition other than 1, 1 + 1 and (1 + 1) occurs as the arc-type of infinitely many connected finite Cayley graphs with the given valency d. As a consequence, this also shows that for every d > 2, there are infinitely many finite zero-symmetric graphs (or GRRs) of valency d.
Keywords: Symmetry type, vertex-transitive graph, arc-transitive graph, Cayley graph, zero-symmetric graph, Cartesian product, covering graph. Math. Subj. Class.: 05E18, 20B25, 05C75, 05C76
*This work was supported by the N.Z. Marsden Fund (via grant UOA1323), and we acknowledge the assistance of Magma [1] in finding and constructing several examples of Cayley graphs with a given arc-type and small valency, as well as in testing various cases. We would also like to thank Joy Morris for asking the question we addressed here, and Gabriel Verret for some helpful discussions about case (d) in Section 4.
E-mail addresses: m.conder@auckland.ac.nz (Marston D. E. Conder), nempoznanovic@gmail.com (Nemanja Poznanovic)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/3.0/
98
ArsMath. Contemp. 15(2018)97-112
1 Introduction
Vertex-transitive graphs hold a significant place in mathematics, and within this, a major role is played by Cayley graphs, which represent groups in a very natural way. A Cayley graph can be defined as any graph that admits some group of automorphisms which acts regularly (sharply-transitively) on the vertices of the graph. Equivalently, a Cayley graph can be constructed from the regular permutation representation of a group G, with vertices taken as the elements of G and edges indicating the effect of a subset S C G (by left multiplication). The set S U S-1 consists of the elements of G that take the identity vertex to one of its neighbours.
It often happens that the automorphism group of a connected finite Cayley graph itself acts regularly on vertices. Any Cayley graph with this property is called a zero-symmetric graph, or a graphical regular representation of the group G, or briefly, a GRR. But of course the automorphism group of a Cayley graph X may be much larger than the vertex-regular subgroup G, and can sometimes even be the full symmetric group on the vertex-set (when the graph is null or complete). Intermediate cases, with Aut(X) larger than G but smaller than Sym(G), as well as other kinds of vertex-transitive graphs, fall into a number of different and interesting classes of graphs, including those that are arc-transitive (or symmetric), and those that are half-arc-transitive (which are vertex-transitive and edge-transitive but not arc-transitive).
A means of classifying vertex-transitive graphs was given in a recent paper by Conder, Pisanski and Zitnik [3], using what is known as the arc-type of the graph. This can be defined as follows.
Let X be a d-valent vertex-transitive graph, with automorphism group A, let Av be the stabiliser in A of any vertex v of X, and consider the orbits of Av on the set of arcs (v, w) with initial vertex v. The Av-orbit of any arc (v, w) can be 'paired' with the Av-orbit of the arc (v, w') whenever (v, w') lies in the same orbit of A as the reverse arc (w, v), and if those two A-obits are the same, then we say the Av-orbit of (v, w) is 'self-paired'. Then the arc-type of X is the partition n of its valency d as the sum
n = ni + n +----+ nt + (mi + mi) + (m2 + +-----+ (ms + ms) (f)
where n1, n2,..., nt are the sizes of the self-paired orbits of Av on arcs with initial vertex v, and m1, m1, m2, m2,..., ms, ms are the sizes of the non-self-paired orbits, in descending order. Similarly, the edge-type of X is the partition of d as the sum of the sizes of the orbits of Av on edges incident with v, and can be found by simply replacing each bracketed term (mj + mj) by 2mj, for 1 < j < s.
For example, if X is arc-transitive, then its arc-type is simply d, while if X is half-arc-transitive, then its valency d is even and its arc-type is (| + |), and X is a GRR if and only if all the terms n and mj in its arc-type are 1.
The authors of [3] also answered the natural question of which arc-types occur for a given valency d. Every vertex-transitive graph of valency 2 is a union of cycles and is therefore arc-transitive, with arc-type 2. Hence in particular, the partitions 1 + 1 and (1 + 1) of 2 do not occur as the arc-type of a vertex-transitive graph. It was shown in [3] that these are the only exceptional cases. Using a construction that takes Cartesian products of pairwise 'relatively prime' vertex-transitive graphs, Conder, Pisanski and Zitnik proved that in all other cases, every partition of d as given in (f) occurs as the arc-type of some vertex-transitive graph X of valency d.
M. D. E. Conder and N. Poznanovic: The arc-types of Cayley graphs
99
In this paper, we prove a much stronger theorem, namely that every such partition other than 1, 1 + 1 and (1 + 1) occurs as the arc-type of infinitely many connected finite Cayley graphs. (This answers a question posed by Joy Morris at the 2015 PhD Summer School in Discrete Mathematics, in Rogla, Slovenia.) As corollaries, we find that every standard partition of a positive integer d is realisable as the edge-type of infinitely many connected finite Cayley graphs of valency d, except for 1 and 1 + 1 (when d < 2), and that for every d > 2, there are infinitely many finite zero-symmetric graphs of valency d.
To prove our main theorem, we adopt the same approach as taken in [3], but show there are infinitely many Cayley graphs that can be used in the construction as building blocks with the required basic type. In particular, we show that the half-arc-transitive Bouwer graphs B(m, k, n) and the 'thickened covers' used in [3] are Cayley graphs, and we construct some new families of Cayley graphs with various arc-types as well.
We begin by setting notation and giving some further background in Section 2. Then in Section 3 we briefly summarise what has to be done to prove our main theorem, which we proceed to do in Section 4. We complete the paper with the consequence for zero-symmetric graphs in Section 5.
2 Preliminaries and further background 2.1 Notation
All the graphs we consider in this paper are finite, simple, undirected and non-trivial (in the sense of containing at least one edge). Given a graph X, we denote by V(X), E(X) and A(X) the set of vertices, the set of edges, and the set of arcs of X, respectively. We denote an edge with vertices u and v by {u, v}, and an arc from u to v by (u, v).
The automorphism group of X is denoted by Aut(X). Note that the action of Aut(X) on the vertex-set V(X) also induces an action of Aut(X) on the edge-set E(X) and one on the arc-set A(X). If the action of Aut(X) is transitive on the vertex-set, edge-set, or arc-set, then we say that X is vertex-transitive, edge-transitive or arc-transitive, and sometimes abbreviate this to 'VT', 'ET' or 'AT', respectively.
Obviously, vertex-transitive graphs are always regular. Moreover, because a disconnected vertex-transitive graph consists of pairwise isomorphic connected components, we may restrict our attention here to connected graphs. An arc-transitive graph is often also called symmetric. A graph is called half-arc-transitive if it is vertex-transitive and edge-transitive, but not arc-transitive. The valency of every half-arc-transitive graph is necessarily even; see [11, p. 59].
Now let G be a group, and let S be a subset of G that is inverse-closed and does not contain the identity element. Then the Cayley graph Cay(G, S) is the graph with vertex-set G, and with vertices u and v being adjacent if and only if vu-1 G S (or equivalently, v = xu for some x G S). Since we require S to be inverse-closed, this Cayley graph is undirected, and since S does not contain the identity, the graph has no loops. Also Cay(G, S) is regular, with valency |S|, and is connected if and only if S generates G. Furthermore, it is easy to see that G acts as a group of automorphisms of Cay(G, S) by right multiplication, and this action is transitive on vertices, with trivial stabiliser, and hence sharply-transitive (or regular). In particular, Cay(G, S) is vertex-transitive.
More generally, a graph X is a Cayley graph for the group G if and only if G acts regularly on V (X) as a group of automorphisms of X. This is very well known — see [10] for example.
100
Ars Math. Contemp. 15 (2018) 113-126
2.2 Cartesian products and (relatively) prime graphs
Given a pair of graphs X and Y (which might or might not be distinct), the Cartesian product X □ Y is a graph with vertex set V(X) x V(Y), such that two vertices (x, y) and (u, v) are adjacent in X □ Y if and only if x = u and y is adjacent with v in Y, or y = v and x is adjacent with u in X. This definition can be extended to the Cartesian product Xi □ • • • □ Xk of a larger number of graphs X1,... ,Xk, which are then called the factors.
A graph X is called prime (with respect to the Cartesian product) if it is not isomorphic to the Cartesian product of a pair of smaller, non-trivial graphs. Every connected graph can be decomposed as a Cartesian product of prime graphs, in a way that is unique up to reordering and isomorphism of the factors; see [6, Theorem 4.9] for a proof. Then two graphs can be said to be relatively prime (with respect to the Cartesian product) if there is no non-trivial graph that is a factor of both. Note that two prime graphs are relatively prime unless they are isomorphic.
For the construction in [3] and here, we need a number of other properties of the Cartesian product, and some ways in which we can tell if a given graph is prime with respect to the Cartesian product. We summarise these as follows:
Proposition 2.1.
(a)	The Cartesian product operation □ is associative and commutative.
(b)	A Cartesian product graph is connected if and only if all its factors are connected.
(c)	If X1,... ,Xk are regular graphs with valencies d1,... ,dk, then their Cartesian product X1 □ • • • □ Xk is also regular, with valency d1 + • • • + dk.
(d)	The Cartesian product ofCayley graphs is a Cayley graph.
(e)	If X1,... ,Xk are connected graphs that are pairwise relatively prime, then Aut(X) = Aut(X1) x • • • x Aut(Xk).
(f)	A Cartesian product of connected graphs is vertex-transitive if and only if all its factors are vertex-transitive.
(g)	If X1,...,Xk are non-trivial connected vertex-transitive graphs with arc-types t1 ,... ,Tk, and X1,... ,Xk are pairwise relatively prime, then the arc-type of their Cartesian product X = X1 □ • • • □ Xk is t1 + • • • + Tk.
Proof. Parts (a) to (c) are easy, and part (d) follows by induction from the fact that
Cay(G,S) □ Cay(H,T) = Cay(G x H, (S x {1H}) U ({1G} x T)). Proofs of parts (e) and (f) can be found in [6], and part (g) was proved in [3].	□
Proposition 2.2. Let X be a Cartesian product of non-trivial connected graphs. Then:
(a)	Every edge of X lies in some 4-cycle in X.
(b)	All the edges in any cycle of length 3 in X belong to the same factor of X.
(c)	If (x, y, z, w) is any 4-cycle in X, then the edges {x, y} and {z, w} belong to the same factor of X, as do the edges {y, z} and {x, w}.
(d)	[The square property] If two edges are incident in X but do not belong to the same factor of X, then there exists a unique 4-cycle in X that contains both of these edges, and this 4-cycle has no diagonals.
M. D. E. Conder and N. Poznanovic: The arc-types of Cayley graphs
101
Proof. Part (a) is easy, and others were proved in [7], for example.	□
Corollary 2.3. Let X be a connected graph. If some edge of X is not contained in any 4-cycle (and in particular, if X has no 4-cycles), then X is prime.
2.3 Thickened covers
Let X be any simple graph, F any subset of the edge-set of X, and m any positive integer. Then the authors of [3] defined the thickened m-cover of X over F as the graph X(F, m) that has vertex-set V(X) x Zm, and edges of two types:
(a)	an edge from (u, i) to (v, i), for every i e Zm and every {u, v} e E(X) \ F,
(b)	an edge from (u, i) to (v, j), for every (i, j) e Zm x Zm and every {u, v} e F.
One can think of this graph as being obtained from X by replacing each vertex of X by m vertices, and each edge by the complete bipartite graph Km,m whenever the edge lies in F, or by mK2 (a set of m 'parallel' edges) whenever the edge does not lie in F.
For example, the thickened 2-cover of the cycle graph C6 over one of its 1-factors is shown in Figure 1.
Figure 1: A thickened 2-cover of C6 (over a 1-factor).
It was shown in [3] that if X is a vertex-transitive graph, and F is a union of orbits of Aut(X) on edges of X, then X(F, m) is vertex-transitive for every m > 2. We can take this further, as follows:
Proposition 2.4. If X = Cay(G, S) is a Cayley graph, and F is an orbit of G on edges of X, then the thickened cover Y = X (F, m) is a Cayley graph for G x Zm.
Proof. We show that Y is exactly the same as the Cayley graph Cay(G x Zm, W), where multiplication in the group G x Zm is given by (g, i)(h, j) = (gh, i + j) for all g, h e G and i, j e Zm, and W is the union of the two sets
Wi = {(s,0): s e S, {1G,s} e F} and W2 = {(t, i) : {1G,t} e F, i e Zm}.
Take any edge of Y of the first kind, say from (u, i) to (v, i) where {u, v} e E(X) \ F. Then v = su for some s e S, and it follows that (v,i) = (su, i) = (s, 0)(u, i), with {1G, s} = {u, su}u-1 = {u, v}u-1 e F. Conversely, if s e S and {1G, s} e F then {u, su} = {1G, s}u e F, and so (s, 0)(u, i) = (su, i) is adjacent to (u, i), for all u and i.
102
Ars Math. Contemp. 15 (2018) 113-126
Similarly, for any edge of the second kind, from (u, i) to (v, j) with {u, v} G F, we have
v = tu for some t G S and so (v, j) = (t, j— i)(u,i) with {1G,t} = {u,v}u-1 G F, and conversely, if {1G,t} G F (where t G S), then {u,tu} = {1G,t}u G F, and therefore (t,j — i)(u, i) = (tu, j) is adjacent to (u, i), for all u, i and j.	□
Also we need some other information about thickened covers, taken from [3]. The fibre over a vertex u of X is the set {(u, i) : i G Zm} of vertices of X(F, m), and any element of this set is said to project onto u. Similarly the fibre over an edge {u, v} of X is the set {{(u, i), (v, i)} : i G Zm} of edges of X(F, m) when {u, v} G E(X) \ F, or the set {{(u,i), (v,j)} : i, j G Zm} when {u,v} G F, and any element of this set is said to project onto {u, v}. The fibre over an arc is defined similarly.
Proposition 2.5. Let X be a vertex-transitive graph, and let F be a union of edge-orbits of X, with the property that every edge in F joins vertices from two different components of X \ F. Then for every two arcs (x, y) and (u, v) from the same arc-orbit of X, any two arcs of X (F, m) that project onto (x, y) and (u, v) respectively lie in the same arc-orbit of X(F,m), for all m > 2.
Proof. See [3, Theorem 7.6].	□
2.4 Bouwer graphs
The first known infinite family of half-arc-transitive graphs of arbitrary even valency greater than 2 was constructed by Bouwer [2] in 1970. These graphs were a sub-family of a wider class of graphs, which we now denote by B(k, m, n), defined as follows.
Let m and n be any integers such that 2m = 1 mod n, with m > 2 and n > 3, and also let k be any integer such that k > 2. Then the vertices of B(k, m, n) may be taken as the k-tuples (a, b) = (a, b2, b3,..., bk) with a G Zm and bj G Zn for 2 < j < k, with any two such vertices being adjacent if and only if they can be written as (a, b) and (a + 1, c) where either c = b, or c = (c2, c3,..., ck) differs from b = (b2, b3,..., bk) in just one position, say position j, where cj = bj + 2°.
Bouwer himself proved in [2] that every such graph is connected, edge-transitive and vertex-transitive, with valency 2k. He also proved that the graphs B(k, 6,9) are half-arc-transitive, and his theorem was extended recently by Conder and Zitnik [4], who proved that B(k, m, n) is arc-transitive only when n = 3, or (k, n) = (2, 5), or (k, m, n) = (2, 3, 7) or (2,6, 7) or (2, 6, 21). In particular, it follows that B(k, m, n) is half-arc-transitive whenever m > 6 and n > 5. Moreover, as shown in [4], if m > 6 and n > 7, then B(k, m, n) has girth 6, and hence in that case, B(k, m, n) is prime.
These prime graphs gave the infinite family of half-arc-transitive graphs with arc-type (k + k), for each k > 2, used in Lemma 8.2 of [3]. We can take this further, by proving the following (which a referee has also pointed out was proved very recently by Ramos Rivera and Sparl in [9]):
Proposition 2.6. Every Bouwer graph B(k, m, n) is a Cayley graph.
Proof. First note that n is odd, since 2m = 1 mod n. Now let G be the semi-direct product Zm k Z^1, where a generator of the complement Zm acts by conjugation from the right on the kernel Z^-1 in the same way as component-wise multiplication by 2. Also let R be the set of all elements of G of the form (1, b), where b is either the zero vector 0 in Z^-1, or one of the elementary basis vectors ej (with all its entries being 0 except for a 1
M. D. E. Conder and N. Poznanovic: The arc-types of Cayley graphs
103
in position j). The k elements of R are non-involutions, whose inverses are the elements of the form (-1, d) where d = 0 or —2-1ej for some i. It follows that the 2k-valent Cayley graph Cay(G, R U R-1) is isomorphic to the Bouwer graph B(k, m, n), for if
(a, b) = (a, b2, b3,..., bk) is any vertex, then (1, 0)(a, b) = (a+1, b), and (1, ej)(a, b) = (a +1, b + 2aej) for all i.	□
3 Main theorem and overview of the proof
As indicated in the Introduction, our main theorem and its first immediate corollary are as follows:
Theorem 3.1. For any positive integer d, let n be any partition of d as given in (f). Then n occurs as the arc-type of infinitely many connected finite Cayley graphs of valency d, except when n is one of the partitions 1, 1 + 1 and (1 + 1) in the cases with d < 2.
Corollary 3.2. With the exception of 1 and 1 + 1 (in the cases with d < 2), every standard partition of a positive integer d is realisable as the edge-type of infinitely many connected finite Cayley graphs ofvalency d.
Corollary 3.2 follows easily from Theorem 3.1. To prove Theorem 3.1, we use much of the proof of the theorem in [3] showing that every such partition is the arc-type of at least one vertex-transitive graph of valency d. In that proof, the given partition n was written as a sum of 'basic' partitions, each having one of a number of forms, and then a VT graph with arc-type n was constructed as a Cartesian product of pairwise relatively prime graphs with arc-types of the associated forms.
This required a good supply of prime vertex-transitive graphs with particular arc-types as 'building blocks', and the following were sufficient.
(a)	Arc-type m: infinitely many prime connected VT graphs, for each integer m > 2;
(b)	Arc-type (m + m): infinitely many prime connected VT graphs, for each m > 2;
(c)	Arc-type m +1: infinitely many prime connected VT graphs, for each m > 2;
(d)	Arc-type 1 + (1 + 1): at least two prime connected VT graphs;
(e)	Arc-type m + (1 + 1): at least one prime connected VT graph, for each m > 2;
(f)	Arc-type 1 + (m + m): at least one prime connected VT graph, for each m > 2;
(g)	Arc-type (1 + 1) + (1 + 1): infinitely many prime connected VT graphs;
(h)	Arc-type (m + m) + (1 + 1): at least one prime connected VT graph, for each m > 2;
(i)	Arc-type 1 + 1 + 1: infinitely many prime connected VT graphs; (j)	Arc-type 1 + 1 + (1 + 1):at least one prime connected VT graph; (k)	Arc-type 1 + 1 + 1 + 1: at least one prime connected VT graph;
(l) Arc-type (1 + 1) + (1 + 1) + (1 + 1):at least one prime connected VT graph.
Now to extend this to a proof of our theorem, we need infinitely many connected finite Cayley graphs of each of the basic forms listed in cases (a) to (l) above.
Such infinite families were provided explicitly for cases (g) and (i) in Lemmas 8.6 and 8.8 of [3]. Also in cases (d), (e) and (g), a single vertex-transitive graph was produced for each m in Lemmas 8.4, 8.5 and 8.7 of [3], as a thickened cover of a particular Cayley graph
104
Ars Math. Contemp. 15 (2018) 113-126
over an edge-orbit. These are Cayley graphs, by Proposition 2.4, but we have to produce infinitely many of them, for each m > 2.
Hence it remains for us to find infinitely many connected finite Cayley graphs in the cases (a)-(f), (h), and (j)-(l) above. We do that in the next section. Specifically, we construct new families of Cayley graphs for cases (a), (d) and (j)-(l), we use the Bouwer graphs for case (b), we show that the thickened covers used in [3] for case (c) are Cayley graphs, and we show that thickened covers of the graphs in cases (d) and (g) provide infinitely many Cayley graphs for cases (e), (f) and (h).
4 Proof of main theorem
As noted earlier, all we need to do to prove Theorem 3.1 is show that there exist infinitely many prime connected finite Cayley graphs with each of the arc-types in the cases listed in the previous section, and then the rest follows by the same argument as in [3, Section 9]. We do this case-by-case below. For completeness, we give a brief description of the Cayley graphs in the cases that do not require any further analysis, and we give more detailed arguments for the rest.
Case (a): Arc-type m, for all m > 2.
For m = 2, we can take the family of all cycle graphs Cn with n > 5. These graphs have arc-type 2, and since they contain no 4-cycles, by part (a) of Proposition 2.2 they are all prime (with respect to the Cartesian product).
For m > 3, we construct an infinite family of arc-transitive prime connected finite Cayley graphs of valency m using the same groups as for this case in [3, Lemma 8.1].
We know by Macbeath's theorem [8] that for every prime p > m, the simple group G = PSL(2,p) is generated by elements x and y such that x2 = ym = (xy)m+4 = 1. Now take S to be the set {x, y-1xy, y-2xy2,..., y-(m-1)xym-1} of all conjugates of x by powers of y, and let X = Cay(G, S).
The elements of S are distinct involutions (since G has trivial centre), and so X has valency |S| = m. Moreover, the subgroup generated by S is normal in (x, y) = G, because x G S and conjugation by y permutes the elements of S among themselves. Hence S generates G, and therefore X is connected. But also conjugation by y induces an automorphism of X that fixes the identity vertex and cyclically permutes its m neighbours among themselves, and so X is arc-transitive. Hence X has arc-type m.
Finally, X is prime, for if it were the Cartesian product of two relatively prime graphs Y and Z, then its arc-type m would be the sum of the arc-types of Y and Z, and if it were the kth Cartesian power of some prime graph Y, then we would find that | V(Y) |k = |V(X)| = |G| = | PSL(2,p)| = p(p2 - 1)/2, which can occur only if k = 1.
Case (b): Arc-type (m + m), for all m > 2.
If n and r are any integers such that 2r = 1 mod n, with n > 7 and r > 6, then by Lemma 8.2 of [3], the Bouwer graph B(m, r, n) is a prime half-arc-transitive graph with arc-type (m + m), for every m > 2. Also by Proposition 2.6 above, this graph is a Cayley graph. Hence in particular, the Bouwer graph B(m, r, n) is a prime Cayley graph with arc-type (m + m), whenever m > 2, r > 6 and n > 7.
Case (c): Arc-type m + 1, for all m > 2.
By Theorem 7.5 of [3], for every integer m > 2 and every integer n > 3, the thickened m-cover of the n-cycle C2n over one of its 1-factors is a prime VT graph with arc-type
M. D. E. Conder and N. Poznanovic: The arc-types of Cayley graphs
105
m + 1 (that is, with two self-paired arc orbits of lengths m and 1). This thickened cover is also a Cayley graph, as we show below.
Let a and b be canonical generators for the dihedral group Dmn of order 2mn, satisfying amn = b2 = (ab)2 = 1, and define Ymn = Cay(Dmn,S) where S is the set {b, ban, ba2n,..., ba(m-1)n, ba}, consisting of m+1 involutions. Now let n be the natural epimorphism from Dmn to Dn = Dmn/Cm with kernel (an} = Cm, and let S and x be the images of S and any x G Dmn under n. Then n induces a graph homomorphism from Ymn to Cay(Dn, S) = Cay(Dn, {b, ba}), which is clearly a cycle of length |Dn | = 2n.
Moreover, the pre-image of an edge of the form {x, bx} is a complete bipartite subgraph of order 2m with m2 edges {xz, bxw} for z, w G (an} = Cm, while the pre-image of an edge of the form {x, bax} is a subgraph of order 2m with m parallel edges {xz, baz} for z G (an} = Cm.
Hence Ymn is isomorphic to the m-thickened cover of C2n used in Theorem 7.5 of [3], and so is a prime Cayley graph with arc-type m + 1, for all m > 2 and all n > 3.
Case (d): Arc-type 1 + (1 + 1).
Let p be any prime such thatp = 1 mod 4, with p > 5, and let k be any integer such that k2 = -1 mod p. Now take G to be the semi-direct product Cp x k C4, which is generated by elements a and b such that ap = b4 = 1 and b-1ab = ak. Note that conjugation by b2 inverts a, while bab-1 = a-k.
Now let X = Cay(G, {b, b-1, ab2}). This graph is 3-valent, since ab2 is an involution, and connected, since (b, ab2} = G. It is also non-bipartite, because if it were bipartite, then its parts would be preserved by the only subgroup of index 2 in G, namely the subgroup generated by a and b2, but that cannot happen since there is an edge from 1 to ab2. We will show that X is prime and has arc-type 1 + (1 + 1), for all p and k.
First, note that the arcs (1, b), (1, b-1) and (1, ab2) can each be extended to a path of length 2 in two ways, namely to (1, b, b2), (1,b, ab3), (1,b-1,b2), (1, b-1,ab), (1, ab2, a-kb3) and (1, ab2, akb). It follows that the edge {1, ab2} lies in no 4-cycle, and in particular, that X is prime. Moreover, the edges {1,b} and {1,b-1} lie in a single 4-cycle up to reversal, namely (1, b, b2, b-1), and so {1, ab2} lies in a different edge orbit from {1, b} and {1, b-1}. On the other hand, the edges {1, b} and {1, b-1} lie in the same orbit of Aut(X), since right multiplication by b-1 takes the former to the latter. Hence the edge-type of X is 2 + 1, and the arc-type of X must be 1 + (1 + 1) or 2 + 1.
Next, we consider the stabiliser A1 in A = Aut(X) of the identity vertex 1. By the above observations, A1 fixes the vertex ab2, as well as b2 (the only other common neighbour of b and b-1) and a-1 (the vertex opposite ab2 in the 4-cycle (ab2, a-kb-1, a-1, akb) containing ab2). By induction and connectedness, A1 fixes every vertex in the orbit of the subgroup H of G generated by a and b2. The latter subgroup has index 2 in G, with coset representatives 1 and b, and if fi is any element of A1 that also fixes the vertex b, then by vertex-transitivity, fi fixes every vertex in the orbit of the coset bH, and hence fixes every vertex, so fi is trivial. It follows that |A1| < 2, and furthermore, since A = GA1 (with G n A1 = {1}), we find that G has index 1 or 2 in A. Hence in particular, G is normal in A (a fact which also follows from a theorem by Zhou and Feng [12, Theorem 2.3] on 3-valent Cayley graphs of order 4p, for p prime).
Now suppose that A1 is non-trivial. Then there exists an automorphism 0 G A1 such that A = (G, 0}, and moreover, 0 has order 2 and must swap the neighbours b and b-1 of 1, and fix ab2. Hence conjugation of G by 0 fixes ab2 and swaps b with b-1 (as elements of G). It follows that 0 fixes b2 and hence also fixes (ab2)b2 = a, but then ak = (ak) =
106
ArsMath. Contemp. 15(2018)97-112
(b 1a6)e = bab 1 = a k, and so ak has order 2, contradiction.
Thus Ai is trivial, and Aut(X) = A = G, so X is a GRR, with arc-type 1 + (1 + 1).
Case (e): Arc-type m + (1 + 1), for all m > 2.
For any prime p = 1 mod 4 with p > 5, and any square root k of —1 mod p, let X be the Cayley graph for Cp x k C4 produced in case (d) above. This graph has two edge-orbits, one of length 4p containing the edge {1, b}, and the other of length 2p containing the edge {1, ab2}, where a and b are generators for G = Cp xk C4 satisfying the relations ap = b4 = 1 and b - 1ab = ak.
Now let Ym = X(F, m) be the thickened m-cover of X over F, where F is the smaller of the two edge-orbits of X. Then Ym is regular of valency m+2, and is a Cayley graph, by Proposition 2.4, so all we have to do is show that Ym is prime and has arc-type m + (1 +1). We do this in much the same way as was done for the single example (for each m) in [3, Lemma 8.4].
First, we note that X \ F is a union of quadrangles (unordered 4-cycles), and every edge of F joins vertices from different quadrangles. Hence by Proposition 2.5, we find that all edges in a fibre over an edge in E(X) \ F lie in the same edge-orbit of Ym, and all edges in a fibre over an edge in F lie in the same edge-orbit. In particular, all edges of the form {(1,0), (ab2,i)} for i G Zm lie in the same edge-orbit of Ym. Also multiplication by (b, 0) puts {(1,0), (b -1, 0)} in the same edge-orbit as {(1,0), (b, 0)}.
On the other hand, up to reversal the edge {(1,0), (b, 0)} lies in just one 4-cycle, namely ((1,0), (b, 0), (b2,0), (b-1,0)), while the edge {(1,0), (ab2,0)} lies in (m — 1)2 distinct 4-cycles, namely ((1,0), (ab2,0), (1,j), (abV)) for j,^ G Zm \ {0}. Hence if m > 2 then {(1,0), (b, 0)} cannot lie in the same orbit as {(1,0), (ab2,0)}. Similarly, when m = 2, up to reversal the edge {(1,0), (b, 0)} lies in precisely four 6-cycles, namely ((1,0), (b, 0), (ab-1,j), (b, 1), (1,1), (abV)) for j,^ G {0,1}, while the edge {(1,0), (ab2,0)} lies in eight 6-cycles, viz. ((1,0), (ab2,0), (1,1), (be, 1), (ab-e,j), (be, 0)) and ((1, 0), (ab2,0), (aekbe, 0), (a1-ekb-e, j), (aekbe, 1), (ab2,1)) for e = ±1 and j G {0,1}, and again we find that the edge {(1,0), (b, 0)} cannot lie in the same orbit as the edge {(1,0), (ab2,0)}.
Hence the edge-type of Ym is m + 2, and its arc-type is m + 2 or m + (1 + 1).
Next, consider the stabiliser A(10) in A = Aut(Ym) of the vertex (1,0). We know that A(10) preserves the set of m neighbours of (1,0) of the form (ab2, i) for i G Zm, and as a consequence, A(10) must preserve the set of all paths of length 2 of the form ((1,0), (ab2, i), y). For any such i, the third vertex y is either (a-kb-1, i), or (akb, i), or (1, j) for some j G Zm \ {0}. Moreover, if y = (a-kb-1, i) or (akb, i), then there is just one path of length 2 from (1,0) to y, while if y = (1, j) for some j, then there are m distinct paths of length 2 from (1,0) to y. Hence A(10) must preserve the set of all vertices (1, j) with j g Zm \ {0}, and so A(10) preserves the fibre over (1,0).
By vertex-transitivity, the same thing holds for every vertex, and so Aut(Ym) permutes the fibres over vertices of X. Hence every automorphism of Ym can be projected to an automorphism of X .In particular, since X has arc-type 1 + (1 + 1), no automorphism can take the arc ((1, 0), (b, 0)) to the arc ((1,0), (b-1, 0)), and thus Ym has arc-type m+(1 +1).
Finally, we show that Ym is prime. To do this, consider any decomposition of Y into Cartesian factors, which are connected and vertex-transitive, by Proposition 2.1. The edge {(1,0), (b, 0)} does not lie in a 4-cycle with any of the m edges of the form {(1,0), (ab2,i)} for i G Zm, and so by part (d) of Proposition 2.2, all of those m edges must lie in the same factor of Ym as {(1,0), (b, 0)}, say Z. The same argument holds for the edge
M. D. E. Conder and N. Poznanovic: The arc-types of Cayley graphs
107
{(1,0), (b-1,0)}, and so this edge must lie in Z as well. Hence Z contains all m + 2 edges incident with the vertex (1,0). By vertex-transitivity and connectedness, all edges of Ym lie in Z, so Z = Ym, and therefore Ym is prime.
Case (f): Arc-type 1 + (m + m), for all m > 2.
This case is similar to the previous one, except that we let Ym = X(F, m) be the thickened m-cover of X where this time F is the larger of the two edge-orbits of X. Again, Ym is a Cayley graph, by Proposition 2.4, but of valency 2m + 1, and all we have to do is show that Ym is prime and has arc-type 1 + (m + m).
The neighbours of the vertex (1,0) are the 2m vertices of the form (b, i) or (b-1, i) where i G Zm, plus the single vertex (ab2,0). It is easy to see that every edge of the form {(1,0), (b±1, i)} lies in many different 4-cycles, while the edge {(1,0), (ab2,0)} lies in no 4-cycles at all. In particular, this shows that Ym is prime, and that the vertex (ab2,0) is fixed by the stabiliser A(10) of (1,0) in A = Aut(Ym). Moreover, X \ F is a union of non-incident edges, and so by Proposition 2.5, all arcs of the form ((1,0), (b, i)) lie in the same arc-orbit of Ym, and the same holds for all arcs of the form ((1,0), (b-1, i)). Hence the arc-type of Ym is either 2m + 1 or 1 + (m + m).
To prove that the arc-type is 1 + (m + m), again we consider the local effect of the stabiliser A(10) on vertices at short distance from the vertex (1,0).
We know that A(10) preserves the set of 2m neighbours of (1,0) of the form (b±1, i) for i G Zm, and fixes the neighbour (ab2,0). In particular, A(10) must preserve the set of all paths of length 2 of the form ((1,0), (b±1, i), y). This time the third vertex y is either (ab3, i), or (ab, i), or (1, or (b2, for some I G Zm, and in the first two cases, there is just one such path of length 2 from (1,0) to y, while if y = (1, or (b2, for some A then there are 2m such paths. Also each vertex v of the form (1, or (b2, lies at distance 3 from the vertex (ab2,0) fixed by A(1j0), via the 2m paths (v, (be, j), (1,0), (ab2, 0)) with e = ±1 and j G Zm. Moreover, if v is one of the vertices of the form (1, ¿), then there are 2m additional paths, namely ((1, ¿), (ab2, (aefcbe, j), (ab2,0)) for e = ±1 and j G Zm, but there are no such additional paths from a vertex of the form (b2,
It follows that no element of A(10) can take a vertex of the form (1, to one of the form (ab3, i) or (ab, i) or (b2, ¿"), and therefore A(10) preserves the fibre over (1,0).
By vertex-transitivity, the same thing holds for every vertex, and hence as before, every automorphism of Ym can be projected to an automorphism of X. In particular, since X has arc-type 1 + (1 + 1), no automorphism can take the arc ((1,0), (b, 0)) to the arc ((1,0), (b-1,0)), and thus Ym has arc-type 1 + (m + m).
Case (g): Arc-type (1 + 1) + (1 + 1).
By Lemma 8.6 of [3], if p is any prime number with p = 1 mod 6, if k is a primitive 6th root of 1 mod p, and G is the semi-direct product Cp xfc C6, generated by two elements a and b of orders p and 6 such that b-1ab = ak, then the Cayley graph
Cay(G, {b, b-1, ab2, (ab2)-1}) is prime and has arc-type (1 + 1) + (1 + 1). In fact, the edges {1, ab2} and {1, (ab2)-1} lie in 3-cycles, but the edges {1, b} and {1, b-1} do not.
Case (h): Arc-type (m + m) + (1 + 1), for all m > 2.
For any prime p = 1 mod 6, and any primitive 6th root k of 1 mod p, let X be the Cayley graph produced in case (g) above. This graph has arc-type (1 + 1) + (1 + 1), and its two edge-orbits both have length 4p, with representatives {1, b} and {1, ab2}, where a and b are generators for G = Cp xfc C6 satisfying ap = b6 = 1 and b-1ab = ak.
108
Ars Math. Contemp. 15 (2018) 113-126
Now let Ym = X(m, F) be the thickened m-cover of X over F, where F is the edge-orbit containing {1, b}, or equivalently, the set of edges that lie in no 3-cycle. This graph is regular, with valency 2m + 2, and by Proposition 2.4 is a Cayley graph, so all we have to do is show it is prime and has arc-type (m + m) + (1 + 1). We do this in the same way as was done for the single example (for each m) in [3, Lemma 8.7].
First, X \ F is a union of triangles (unordered 3-cycles), and every edge of F joins vertices from different triangles, and it follows that every automorphism of Ym induces a permutation of the fibres over the edges in E(X) \ F, and also a permutation of the fibres over the edges in F. On the other hand, Proposition 2.5 tells us that all edges in a fibre over an edge in E(X) \ F lie in the same edge-orbit, and all edges in a fibre over an edge in F lie in the same edge-orbit. Hence the edge-type of Ym is 2m + 2.
Next, from vertex (u, i) in Ym there are precisely 2m paths from (u, i) to any other vertex (u, in the fibre over (u, i), namely those of the form ((u, i), (bu, j), (u, ¿)) and ((u, i), (b-1u, j), (u, ¿)) for each j G Zm, while on the other hand, there are only one, two or m paths from (u, i) to any other vertex v at distance 2 from (u, i). Hence the stabiliser in Aut(Ym) of the vertex (u, i) preserves the fibre over the vertex u, and it follows that Aut(Ym) permutes the fibres over the vertices of X.
Thus every automorphism of Ym can be projected to an automorphism of X, and the arc-type of Ym is (m + m) + (1 + 1), as required.
Finally, we show that Ym is prime. If Ym were the Cartesian product of two relatively prime graphs, then one of them would have arc-type (1 + 1), which is impossible. On the other hand, if Ym were a proper Cartesian power of some prime graph Z, say Ym = Zr with r > 2, then by part (b) of Proposition 2.2, all edges in a 3-cycle of Ym would lie in the same factor of Ym, so Z would contain a 3-cycle, but in that case a vertex of Ym = Zr would lie in at least two triangles, contradiction. Thus Ym is prime.
Case (i): Arc-type 1 + 1 + 1.
By Lemma 8.8 of [3], if n is any odd integer greater than 11, and G is the dihedral group Dn, generated by two elements x and y satisfying x2 = yn = 1 and xyx = y-1, then Cay(G, {x, xy, xy3}) is prime and has arc-type 1 + 1 + 1.
Case (j): Arc-type 1 + 1 + (1 + 1).
This is similar to case (d). Let p be any prime such that p = 1 mod 4, with p > 5, let k be any integer such that k2 = — 1 mod p, and let G be the semi-direct product Cp x k C4, generated by two elements a and b such that ap = b4 = 1 and b-1ab = ak. Now take S = {b, b-1, ab2, a2 b2}, which consists of an inverse pair of elements of order 4 and two involutions (as conjugation by b2 inverts a), and let X = Cay(G, {b, b-1, ab2, a2b2}).
Then X is 4-valent and connected, since (b, ab2} = G, and is also non-bipartite, just as in case (d). We will show that X is prime and has arc-type 1 + 1 + (1 + 1).
First, by considering the vertices at distance 2 from the identity we see that up to reversal, the edges {1, b} and {1, b-1} lie in a single 4-cycle, namely (1, b, b2, b-1), while each of the edges {1, ab2} and {1, a2b2} lies in no 4-cycle. In particular, it follows from the latter observation that X is prime.
Also as before, the edges {1,b} and {1,b-1} lie in the same edge-orbit. On the other hand, the edges {1,ab2} and {1,a2 b2} lie in different edge orbits, because up to reversal the edge {1, ab2} lies in four 5-cycles, namely those of the form (1, ab2, u, v, w) with (u,v,w) = (a, b2,b), (a, b2,b-1), (akb, a-1, a2b2) and (a-kb-1, a-1, a2b2), while the edge {1, a2b2} lies in only two 5-cycles, namely those of the form (1, a2b2, u, v, w)
M. D. E. Conder and N. Poznanovic: The arc-types of Cayley graphs
109
with (u,v,w) = (a \akb, ab2) and (a 1,a kb 1,a62). Hence the edge-type of X is 2 + 1 + 1.
This also implies that every automorphism of X preserves the set T = {x, a2b2x} of all edges corresponding to left multiplication by the element a2b2 G S, and hence induces an automorphism of the subgraph obtained by removing those edges, namely Cay(G, S \ T) = Cay(G, {b, b-1, ab2}). By case (d), however, the latter subgraph is a GRR, with automorphism group G, and so every such automorphism is given by right multiplication by some element of G. It follows that G = Aut(X), and hence X is also a GRR, and has arc-type 1 + 1 + (1 + 1).
Case (k): Arc-type 1 + 1 + 1 + 1.
For any integer n > 15, let G be the dihedral group Dn, generated by elements a and b such that an = b2 = (ab)2 = 1, and take S = {b, ba, ba2, ba5}. Then since S consists of four involutions and G is generated by b and ba, the graph X = Cay(G, S) is 4-valent and connected. We show that X is prime and has arc-type 1 + 1 + 1 + 1.
First, the paths of length 2 in X starting at the identity vertex 1 are (1, b, a?) for j G {-1, -2, -5}, and (1, ba, a?) for j G {1, -1, -4}, and (1, ba2, a?) for j G {2,1, -3}, and (1, ba5, a?) for j G {5,4,3}. By considering the final vertex of each of these, we see that the vertex 1 lies in only two 4-cycles up to reversal, namely (1, b, a-1, ba) and (1, ba, a, ba2). Hence the edges {1, b} and {1, ba2} lie in just one 4-cycle, while {1, ba} lies in two 4-cycles, and {1, ba5 } lies in no 4-cycles at all. In particular, X is prime, and also X has edge-type 1 + 1 + 1 + 1 or 2+1 + 1, with each of {1, ba} and {1, ba5} lying in different orbits from each other and from {1, b} and {1, ba2}.
Next, multiplying by b, we find that ba5b = a-5 plays the same role for the vertex b as ba5 does for the vertex 1, namely that {b, a-5} is the only edge incident with b that lies in no 4-cycle. Now consider the cycles of length 6 containing one of the paths (ba5,1, b), (a-5, b, 1) and (ba5,1, ba2). An easy calculation shows there are precisely three 6-cycles of the form (ba5,1, b, u, v,w), namely with (u,v,w) = (a-1, ba4, a3), (a-1,ba4,a4) and (a-1, ba3, a3), and similarly, there are three 6-cycles of the form (a-5, b, 1, u, v, w), namely with (u, v, w) = (ba, a-4, ba-3), (ba, a-4, ba-4) and (ba2, a-3, ba-3), but there are seven 6-cycles of the form (ba5,1, ba2, u, v, w), namely with (u, v, w) = (a, ba3, a3), (a, ba6, a4), (a, ba6, a5), (a2, ba3, a3), (a2, ba4, a3), (a2, ba4, a4) and (a2, ba7, a5).
In fact, up to reversal the edge {1, b} lies in 16 different 6-cycles altogether, while the edge {1, ba2} lies in 20 different 6-cycles, but this takes more work to verify.
Both calculations show that the edge {1, ba2} cannot lie in the same orbit as {1, b} under Aut(X), and it follows that X has edge-type and arc-type 1 + 1 + 1 + 1.
Case (l): Arc-type (1 + 1) + (1 + 1) + (1 + 1).
This is somewhat similar to case (g). Let p be any prime with p = 1 mod 6, but this time where p > 7, let k be a primitive 6th root of 1 mod p, with k3 = -1 mod p, and let G be the semi-direct product Cp x k C6, generated by two elements a and b of orders p and 6 such that b-1ab = ak. Now take S = {b, ab2, a2b2, b-1, a-k b4, a-2k b4}, which consists of the elements b, ab2 and a2b2 and their inverses, and let X = Cay(G, S). Then clearly X is 6-valent and connected. We will show that X is prime, and has arc-type (1 + 1)+ (1 + 1)+ (1 + 1), for all p.
First we note that {1, s} and {1, s}s-1 = {1, s-1} lie in the same edge orbit of X, for each s g S. Hence X has at most three distinct edge orbits.
Next, up to reversal the edge {1, b} lies in just two 4-cycles, namely (1, b, ab3, a-k b4)
110
Ars Math. Contemp. 15 (2018) 113-126
and (1, b, a2b3, a-2k2b4), and multiplying by b-1 gives the two 4-cycles containing the edge {1, b-1} as (1, b-1, a-k b3, ab2) and (1, b-1, a-k b3, a2b2). Each of the other four edges incident with the vertex 1 is contained in only one 4-cycle (up to reversal), namely one of the four just listed for {1, b} and {1, b-1}. Hence the orbit of the edges {1, b±1} under Aut(X) is different from the orbit(s) of {1, s±1} for s = ab2 and s = a2b2.
Also the edge {1, ab2} lies in five 5-cycles, viz. those of the form (1, ab2, u, v, w) with (u,v,w) = (akb, ak-1, a2b2), (ak b,a-k b-1,a-k2 b4), (a-k 2 b3,ab,b-1), (a-k+1,b2,b), and (a-k b4, ab3, b), while the edge {1, a2b2} lies in only four 5-cycles, namely those of the form (1,a2b2,u,v,w) with (u,v,w) = (ak-1,akb,ab2), (a2kb,a-2kb-1 ,a-2k2b4), (a-2k b3, a2b, b-1) and (a-2k b4, a2b3, b). Hence the orbit of the edges {1, (ab2)±1} is different from the orbit of {1, (a2b2)±1}, and so the edge-type of X is 2 + 2 + 2.
But furthermore, if there exists an automorphism of X that fixes the vertex 1 and swaps b with b-1, then that automorphism must swap the two 4-cycles (1, b, ab3, a-k b4) and (1, b, a2b3, a-2k2b4) with the two 4-cycles (1, b-1,a-kb3, ab2) and (1, b-1,a-k2 b3, a2b2), and hence must swap ab2 with a-k b4 = (ab2)-1 and swap a2b2 with a-2k b4 = (a2b2)-1. Similarly, if if there exists an automorphism that fixes 1 and swaps ab2 with a-k b4, then it must swap the 4-cycle (1,b-1,a-k b3, ab2) with the 4-cycle (1, b, ab3, a-k b4), and hence must swap b with b-1, and the same holds for a2b2 and a-2k b4.
It follows that any automorphism that fixes the vertex 1 must either fix all its six neighbours, or induce the triple transposition (b, b-1)(ab2,a-k b4)(a2b2, a-2k b4) on them. By vertex-transitivity, the analogous thing happens at every vertex, and an easy argument then shows that the stabiliser A1 in A = Aut(X) of the vertex 1 acts faithfully on its neighbourhood, and therefore | A11 = 1 or 2.
Now suppose that |A1| = 2. Then |A| = |GA1| = 2|G|, and so G is normal in A. Hence if 0 is any non-trivial element of A1, then 0 normalises G, and so induces an automorphism of G = {a, b). Moreover, as 0 fixes the vertex 1 and acts non-trivially on its neighbourhood, we find that 0 swaps b with b-1, and ab2 with a-k b4 = (ab2)-1. In turn, this implies that 0 swaps a = (ab2)b-2 with a-k b4b2 = a-k , but then we find that ak = (ak)e = (b-1ab)6 = ba-k b-1 = a-k, and so ak has order 2, contradiction.
Thus A1 is trivial, and Aut(X) = G, so X has arc-type (1 + 1) + (1 + 1) + (1 + 1).
Finally, X cannot be the Cartesian product of two smaller graphs that are relatively prime, since those would have to be connected and vertex-transitive, and one of them would have arc-type (1 + 1), which is impossible. Also X cannot be a Cartesian power of some smaller VT graph, since its order 6p is not a non-trivial power of any integer. Hence X is prime, as required.
Accordingly, we have infinitely many connected finite Cayley graphs with each of the basic arc-types, and this completes the proof of Theorem 3.1 and Corollary 3.2.
For the benefit of the reader (and for possible future reference), we summarise some of the details of the basic arc-types used here, in Table 1.
5 A consequence for zero-symmetric graphs
Another consequence of Theorem 3.1 is the following:
Corollary 5.1. For every integer d > 2, there exist infinitely many finite zero-symmetric graphs (or GRRs) of valency d.
M. D. E. Conder and N. Poznanovic: The arc-types of Cayley graphs
111
Table 1: Summary of some Cayley graphs with the basic arc-types.
Arc-type	Cayley graphs
m	Cycle graphs Cn (n > 5) for m = 2, and Cayley graphs for PSL(2,p) via m conjugate involutions for m > 3
(m+m)	Bouwer graphs B(m, r, n) with n > 7 and r > 6
m+1	Thickened m-cover of C2n over a 1-factor
1 + (1 + 1)	3-valent Cayley graph for Cp x k C4 (for prime p)
m+(1 + 1)	Thickened cover of Cayley graph for Cp x k C4
1 + (m+m)	Thickened cover of Cayley graph for Cp x k C4
(1 + 1) + (1 + 1)	4-valent Cayley graph for Cp x k C6 (for prime p)
(m+m) + (1 + 1)	Thickened cover of Cayley graph for Cp x k C6
1 + 1 + 1	3-valent Cayley graph for dihedral groups Dn
1 + 1 + (1 + 1)	4-valent Cayley graph for Cp x k C4 (for prime p)
1+1+1+1	4-valent Cayley graph for dihedral groups Dn
(1 + 1) + (1 + 1) + (1 + 1)	6-valent Cayley graph for Cp x k C6 (for prime p)
This is not at all surprising, but appears to be new, in the sense that we cannot find the statement or something similar in the literature on GRRs or zero-symmetric graphs. It is shown in [5, Theorem 3.10.4] that there exists a GRR of valency d for the symmetric group Sd+1 whenever the latter group can be generated by an 'asymmetric' set of d transpositions. The latter happens for all d > 5, but gives only finitely many GRRs with given valency d. On the other hand, it is clear that larger sets of involutory generators for dihedral or symmetric or other groups will give GRRs, even if this does not appear to have been explicitly proved elsewhere.
References
[1]	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.
[2]	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.
[3]	M. D. E. Conder, T. Pisanski and A. Zitnik, Vertex-transitive graphs and their arc-types, Ars Math. Contemp. 12 (2017), 383-413, doi:10.26493/1855-3974.1146.f96.
[4]	M. D. E. Conder and A. Zitnik, Half-arc-transitive graphs of arbitrary even valency greater than 2, European J. Combin. 54 (2016), 177-186, doi:10.1016/j.ejc.2015.12.011.
[5]	C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9.
[6]	W. Imrich and S. KlavZar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
[7]	W. Imrich and I. Peterin, Recognizing Cartesian products in linear time, Discrete Math. 307 (2007), 472-483, doi:10.1016/j.disc.2005.09.038.
112
Ars Math. Contemp. 15 (2018) 113-126
[8]	A. M. Macbeath, Generators of the linear fractional groups, in: W. J. LeVeque and E. G. Straus (eds.), Number Theory, American Mathematical Society, Providence, Rhode Island, volume 12 of Proceedings of Symposia in Pure Mathematics, pp. 14-32, 1969, http://www.ams. org/books/pspum/012/02 62 37 9.
[9]	A. Ramos Rivera and P. Sparl, The classification of half-arc-transitive generalizations of Bouwer graphs, European J. Combin. 64 (2017), 88-112, doi:10.1016/j.ejc.2017.04.003.
[10]	G. Sabidussi, On a class of fixed-point-free graphs, Proc. Amer. Math. Soc. 9 (1958), 800-804, doi:10.2307/2033090.
[11]	W. T. Tutte, Connectivity in Graphs, volume 15 of Mathematical Expositions, University of Toronto Press, Toronto, Ontario, 1966.
[12]	C. Zhou and Y.-Q. Feng, Automorphism groups of connected cubic Cayley graphs of order 4p, Algebra Colloq. 14 (2007), 351-359, doi:10.1142/s100538670700034x.