ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 1-31
https://doi.org/10.26493/1855-3974.1815.b52
(Also available at http://amc-journal.eu)
Classification of cubic vertex-transitive tricirculants*
*
Primož Potočnik ©
University of Ljubljana, Faculty of Mathematics and Physics, Jadranska 21, SI-1000 Ljubljana, Slovenia
Micael Toledo ©
Institute ofMathematics, Physics and Mechanics, Jadranska 19, SI-1000, Slovenia, and University ofPrimorska, Faculty ofMathematics, Natural Sciences and Information Technologies, Glagoljaška 8, SI-6000 Koper, Slovenia
Received 4 October 2018, accepted 30 October 2019, published online 29 May 2020
A finite graph is called a tricirculant if admits a cyclic group of automorphism which has precisely three orbits on the vertex-set of the graph, all of equal size. We classify all finite connected cubic vertex-transitive tricirculants. We show that except for some small exceptions of order less than 54, each of these graphs is either a prism of order 6k with k odd, a Mobius ladder, or it falls into one of two infinite families, each family containing one graph for every order of the form 6k with k odd.
Keywords: Graph, cubic, semiregular automorphism, tricirculant, vertex-transitive. Math. Subj. Class. (2020): 05E18, 05C25
1 Introduction
All graphs in this paper are finite. A connected graph r admitting a cyclic group of automorphisms H having k orbits of vertices of equal size larger than 1 is called a k-multicirculant and a generator of H is then called a k-multicirculant automorphism of r. In particular, 1-, 2- and 3-multicirculants are generally called circulants, bicirculants and tricirculants, respectively. A graph is called cubic if it is connected and regular of valence 3.
*The authors gratefully acknowledge support of the Slovenian Research Agency by financing the Research program P1-0294 and the second listed author Young Researcher scholarship.
E-mail addresses: primoz.potocnik@fmf.uni-lj.si (Primož Potočnik), micaelalexitoledo@gmail.com (Micael Toledo)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
34
Ars Math. Contemp. 18 (2020) 2-49
A famous and longstanding polycirculant conjecture claims that every vertex-transitive graph and digraph is a k-multicirculant for some k (see [3, 13, 14, 15]). It is particularly interesting to study conditions under which vertex-transitive graphs admit k-multicirculant automorphisms of large order (and thus relatively small k); see, for example, [2, 20]. On the other hand, existence of a k-multicirculant automorphism with small k often restricts the structure of a vertex-transitive graph to the extent that allows a complete classification. There is a series of classification results about cubic arc-transitive k-multicirculant for k < 5 (see [7, 10]). In particular, cubic arc-transitive tricirculants where completely classified in [1( ], where it was shown that only 4 such graphs exist: K3 3, the Pappus graph, Tutte's 8-cage and a graph on 54 vertices. This work culminated in a beautiful paper [9], where it was shown that for all square-free values of k coprime to 6 there exist only finitely many cubic arc-transitive k-multicirculants.
In this paper we widen the focus to a much wider and structurally richer class of cubic vertex-transitive graphs that are not necessarily arc-transitive. It is know that every cubic vertex-transitive graph has a k-multicirculant automorphisms [16] and that no fixed k exists such that every cubic vertex-transitive graph is a k-multicirculant [20]. As for the classification results, it is clear that a cubic graph is a vertex-transitive 1-circulant if and only if it is a cubic Cayley graph on a cyclic group. Furthermore, vertex-transitive cubic bicirculants were classified in [17]. The goal of this paper is to provide a complete classification of cubic vertex-transitive tricirculants.
The following theorem and remarks are a brief summary of the contents of this paper.
Theorem 1.1. A cubic graph r is a vertex-transitive tricirculant if and only if the order of r is 6k for some positive integer k and one of the following holds:
1.	k > 1, k is odd and r is isomorphic to one of the graphs X(k) or Y(k), described in Section 4 (Definition 4.1) and Section 5 (Definition 5.1 ), respectively.
2.	r is a prism and k is odd, or r is a Möbius ladder (defined in Section 6).
3.	r is the truncated tetrahedron or Tutte's 8-cage.
Remark 1.2. All Möbius ladders are circulants. A prism Pk is a circulant whenever k is odd. Meanwhile X(k) and Y(k) are bicirculants if and only if k is odd and 3 \ k. In this case, X(k) is isomorphic to the generalized Petersen graph GP(3k, k + (-1)a) while Y(k) is isomorphic to the graph H(3k, 1, ak + 2), where a G {1,2} and a = k (mod 3) (see [17] for definitions pertaining to bicirculant graphs).
Remark 1.3. Y(k) can be embedded on the torus yielding the toroidal map {6, 3}a,3 where a = 1 (k - 1) (see [ ] for the definitions pertaining to the maps on the torus).
Remark 1.4. For k > 7, the graphs X(k) and Y(k) have girth 8 and 6, respectively. Meanwhile, prisms and Möbius ladders have girth 4. The graph X(k) is not bipartite for any integer k, while Y(k) is bipartite for all odd k > 1.
Remark 1.5. There are exactly four cubic arc-transitive tricirculants: K3 3, the Pappus graph, Tutte's 8-cage and the graph with 54 vertices denoted F054A in [1]. All other cubic vertex-transitive tricirculants have two edge orbits and their arc-type is 2+1 (see [4] for details). There are no semi-symmetric cubic tricirculants.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
3
2 Diagrams
Even though this paper is about simple graphs, it will be convenient in the course of the analysis to have a slightly more general definition, which allows the graphs to have loops, parallel edges and semi-edges. To distinguish between a simple graph (which we will refer to simply as a graph) and these more general objects, that we shall call pregraphs. In what follows, we briefly introduce the concept of a pregraph and refer the reader to [11, 12] for more detailed explanation.
A pregraph is an ordered 4-tuple (V, D; beg, inv) where D and V = 0 are disjoint finite sets of darts and vertices, respectively, beg: D ^ V is a mapping which assigns to each dart x its initial vertex beg x, and inv: D ^ D is an involution which interchanges every dart x with its inverse dart, also denoted by x-1. The neighbourhood of a vertex v is defined as the set of darts that have v for its initial vertex and the valence of v is the cardinality of the neighbourhood. Note that a simple graph r can be represented as a pregraph by letting V = V(r) be the vertex-set of r, letting D = {(u, v) : u, v e V(r), u v} be the arc-set of r, and by letting beg(u, v) = u and inv(u, v) = (v,u). Notions such as morphism, isomorphism and automorphism of pregraphs are obvious generalisations of those for (simple) graphs and precise definitions can be found in [11, 12].
The orbits of inv are called edges. The edge containing a dart x is called a semi-edge if inv x = x, a loop if inv x = x while beg (x-1) = beg x, and is called a link otherwise. The endvertices of an edge are the initial vertices of the darts contained in the edge. Two links are parallel if they have the same endvertices. When we present a pregraph as a drawing, the links are drawn in the usual way as a line between the points representing its endvertices, a loop is drawn as a closed curve at its unique endvertex and a semi-edge is drawn as a segment attached to its unique endvertex. The following lemma, which will serve as the starting point of our analysis of cubic tricirculants, is an easy exercise illustrating the definition of a pregraph.
Lemma 2.1. Up to isomorphism there are precisely four non-isomorphic cubic pregraphs on three vertices such that no vertex is the initial vertex of more than one semi-edge, namely the pregraphs A1, A2, A3 and A4 depicted in Figure 1.
Figure 1: Cubic pregraphs on three vertices without parallel semi-edges.
Given a pregraph r and a group H < Aut(r) we define the quotient r/H to be the pregraph (V', D'; beg', inv') where V' and D' are the sets V(r)/H and D(r)/H of orbits of H on V and D, respectively, and beg' and inv' are defined by beg'(xH) = (beg x)H and inv'(xH) = (inv x)H for every x e D(r). The mapping ph : V(r) U D(r) ^ V' U D' that maps a vertex or a dart x to its H-orbit xH is then an epimorphism of pregraphs, called the quotient projection with respect to H. If H acts semiregularly on V(r) (that is, if the vertex-stabiliser Hv is trivial for every vertex v e V(r)), then the quotient projection pH
34
Ars Math. Contemp. 18 (2020) 4-49
is a regular covering projection and in particular, it preserves the valence of the vertices. Moreover, in this case the graph r is isomorphic to the derived covering graph of r/H, a notion which we now define.
Let r' = (V', D', beg', inv') be an arbitrary connected pregraph, let N be a group and let Z: D' ^ N be a mapping (called a voltage assignment) satisfying the condition Z(x) = Z(inv' x)-1 for every x G D'. Then Cov(r', Z) is the graph with D' x N and V' x N as the sets of darts and vertices, respectively, and the functions beg and inv defined by beg(x, a) = (beg' x, a) and inv(x, a) = (inv' x, aZ(x)). If, for a voltage assignment Z: D(r') ^ N, there exists a a spanning tree T in r' such that Z(x) is the trivial element of N for every dart x in T, then we say that Z is normalised; note that in this case Cov(r', Z) is connected if and only if the images of Z generate N. The following lemma is a well-known fact in the theory of covers:
Lemma 2.2. Let H be a group of automorphisms acting semiregularly on the vertex-set of a connected graph r, let r' = r/H and let T be a spanning tree in r'. Then there exists a voltage assignment Z: D(r') ^ N which is normalised with respect to T and such that
r = Cov(r', z ).
Let us now move our attention back to cubic tricirculants. Consider the voltage assignments Zi: Ai ^ Z2k given in Figure 2 where the value Zi (x) is written next to the drawing of each dart x G D(Ai).
Lemma 2.3. Let r be a cubic tricirculant, let p be a corresponding tricirculant automorphism and let n be the order of p. Then n = 2k for some positive integer k and there exist elements r, s G Zn andi G {1,2, 3,4} such that r = Cov(Ai, Zi) where Zi: D(Ai) ^ Zn is the voltage assignment defined by Figure 2.
Proof. Note first that the quotient r/(p) is a pregraph with three vertices of valency 3, one for each orbit under the action of (p). Since p is a semiregular automorphism of r of order n, the group (p) is isomorphic to Zn and acts semiregularly on V(r). By Lemma 2.2, r = Cov(r/(p),Z) for some voltage assignment Z: D(r/(p), Zn). Note that by definition of voltage assignments, it follows that Z (x) = —Z (x-1) for every x G D(r/(p)), implying that if x is a semi-edge, then Z(x) is an element of order at most 2 in Zn, and since r has no semi-edges, Z(x) must in fact have order 2 in Zn. Since every pregraph with three vertices in which every vertex has valence 3 contains at least one semi-edge, it follows that n = 2k for some positive integer k, and moreover, Z(x) = k for every semi-edge x of r/ (p). Since r has no parallel edges, this also implies that every vertex of r/(p) is the initial vertex of at most one semi-edge. By Lemma 2.1, r/(p) = Ai for some i G {1,2,3,4} and we may thus assume that r = Cov(Ai, Zi) for some i G {1, 2,3,4} and some voltage assignment Zi: Ai ^ Zn. Finally, in view of Lemma 2.2, we may assume that Zi(x) = 0 for every edge x belonging to a chosen spanning tree of Ai. In particular, Zi can be chosen as shown in Figure 2.	□
A cubic tricirculant isomorphic to Cov(Ai, Zi), i G {1, 2,3,4}, is said to be of Type i and is denoted by Ti(k, r, s), if i = 3, or T3(k, r). From Lemma 2.3 we get the following characterization of connected cubic tricirculants.
Theorem 2.4. A cubic graph r is a tricirculant if and only if n = 6k and it is isomorphic to Ti(k, r, s) or T3(k, r), for some i G {1, 2,4} and r, s G Z2k. Furthermore, Ti(k, r, s)
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants	5
(Al ,Cl)	(A2 ,Z2 )
k k
(As ,Cs )	(A4 ,Z4)
Figure 2: The voltage assignments giving rise to cubic tricirculants.
is connected if and only if gcd(2k, k, r, s) = 1 while T3 (k, r) is connected if and only if gcd(2k, k, r) = 1.
Note that in principle, a cubic tricirculant could be of more than one type. However, each vertex-transitive cubic tricirculant is of Type i for exactly one i G {1, 2, 3, 4}, with the exception of the triangular prism P3 which is both of Type 1 as well as of Type 3.
The following sections are devoted to the analysis of the tricirculants graphs arising from the voltage assignments Q, and in particular, to determining sufficient and necessary conditions for vertex-transitivity. We will consider the graphs of order at most 48 separately in Section 3 and as for the graphs of larger order, we will show that no graph of Type 4 is vertex-transitive, that Type 3 yields prisms and Möbius ladders, and that Types 1 and 2 each yield one infinite family of vertex-transitive graphs, namely the graphs X(k) defined in Definition 4.1 and the graphs Y(k) defined in Definition 5.1.
Finally, to facilitate discussion in the forthcoming sections, we specify the notion of a walk. A walk u in a (pre)graph is a sequence of darts (#i, x2,..., xn) such that beg(xi+1) = beg(x-1) for all i G {1,..., n — 1}; that is, the initial vertex of xi+1 is the end vertex of x. We say that u is closed if the initial vertex of x1 is the endvertex of xn. If additionally beg(x^) = beg(xj) for all i = j, then we say that u is a cycle. We define the inverse of u as the walk u-1 = (x-1, x-i1,..., x-1). We say that a walk u is a reduced walk if no two consecutive arcs are inverse to one another (if u is closed, we will consider the first arc and the last arc of u to be consecutive). It is pertinent to point out that, from this definition, all walks and cycles are directed and have an initial vertex. Therefore, no reduced walk is equal to its inverse.
34
Ars Math. Contemp. 18 (2020) 6-49
3 Graphs of small order
To make this classification as general and as neat as possible, we will treat cubic tricirculant graphs of small order separately, as if we allow graphs that are "too small", special cases and exceptions will inevitably occur. Since a cubic tricirculant must have order 6k, for some positive k, we present, in Table 1, the complete list of all cubic vertex-transitive tricirculants of order at most 48 obtained from the census [18] of cubic vertex-transitive graphs. Notice that with the exception of the truncated tetrahedron, Tr(K4), of order 12 and Tutte's 8-cage, T8, of order 30 (see Figure 3), all vertex-transitive cubic tricirculants of order at most 48 are isomorphic to either X(k), Y(k), Pk (the prism of order 2k) or Mk (the Möbius ladder of order 2 k) for some integer k.
Table 1: Graphs of small order.
Order	Type	Graph	Order	Type	Graph	Order	Type	Graph
6	1, 3	P3	18	3	M9	36	3	Mis
6	3	M3	24	3	M12	42	1	X(7)
12	1	Tr(K )	30	1	X(5)	42	2	Y(7)
12	3	Ma	30	2	Y(5)	42	3	P21
18	1	X(3)	30	3	Pl5	42	3	M21
18	2	Y(3)	30	3	M15	48	3	M24
18	3	P9	30	4	T8			
Figure 3: The truncated tetrahedron Tr(K4) and Tutte's 8-cage.
The graphs K3,3, Y(3) (the Pappus graph) and Tutte's 8-cage are arc-transitive. The fourth arc-transitive cubic tricirculant, denoted F054A in [1], does not appear in Table 1, as it has 54 vertices; it corresponds to the graph Y(9) defined in Section 5. The four aforementioned graphs are the only edge-transitive cubic tricirculants. Indeed, a cubic graph that is both vertex- and edge-transitive is automatically arc-transitive [22]. A graph that is edge-transitive but not vertex-transitive is called a semi-symmetric graph, and must have two orbits of vertices under its full automorphism group [6]. It follows that no tricirculant can be semi-symmetric, as its tricirculant automorphism would mix the two vertex orbits, making the graph vertex-transitive.
For the remainder of this paper, all cubic tricirculants will have order at least 54.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
7
4 Type 1
Let k > 9 be an integer, and let r and s be two distinct elements of Z2k. Recall that T1 (k, r, s) is the covering graph arising from (Ai, Zi) shown in Figure 2; for convenience, we repeat the drawing here (see Figure 4).
Figure 4: The voltage assignment giving rise to the graph T1 (k, r, s).
By the definition of a derived cover, the vertices of Ti (k, r, s) are then the pairs (x, i) where x e {u, v, w} is a vertex of A1 and i e Z2k. Note that Ti (k, r, s) is connected if and only if k, r and s generate Z2k, that is, if and only if gcd(k, r, s) = 1.
To simplify notation, we write ui instead of (u, i) and similarly for vi and wi. Then U = {uo,ui,... ,U2k-i}, V = {vo, vi,..., V2k-1} and W = {wo, wi, ..., W2k-i} are the respective fibres of vertices u, v and w, and the edge-set of Ti (k, r, s) is then the union of the sets
Ek = {uiui+k : i e Z2k}, Eo = {uivi : i e Z2k} U {uiwi : i e Z2k}, Er = {viwi+r : i e Z2k},
Es = {viwi+s : i e Z2k}.
Definition 4.1. For an odd integer k > 1, let
' k+3
^i3 + k, if k = 3 (mod 4)
r* ^ 2
^^, if k = 1 (mod 4)
and let X(k) = Ti (k,r*, 1).
We can now state the main theorem of this section.
Theorem 4.2. Let k > 9 and let r be a connected cubic tricirculant of Type 1 with 6k vertices. Then the following holds:
(1)	r is vertex-transitive if and only if it is isomorphic to X(k) with k odd.
(2)	If r is not vertex-transitive, then it has two vertex orbits under its full automorphism group, one twice the size of the other.
The next theorem gives more information about the graph X(k).
Theorem 4.3. Let k be an odd integer, k > 1. Then the following holds:
34
Ars Math. Contemp. 18 (2020) 8-49
(1)	X(k) is a bicirculant if and only if 3 { k, in which case it is isomorphic to the generalized Petersen graph GP(3k, k + ( — 1)a) where a G {1, 2} and a = k (mod 3).
(2)	X(k) has arc-type 2+1.
The rest of the section is devoted to the proof of Theorems 4.2 and 4.3. Clearly, as a tricirculant of Type 1, r is isomorphic to T1(k,r, s) for some integer k and elements r,s G Z2k (see Lemma 2.3). We shall henceforth assume that r = T1(k, r, s) for some k > 9 and that r is connected. For a symbol X from the set of symbols {0, R, S, K}, edges in EX will be called edges of type X, or simply X-edges.
Define p as the permutation given by p(uj) = ui+1, p(vi) = vi+1 and p(wj) = wi+1, and note that p is a tricirculant automorphism of T1(k,r, s). Further, observe that
Ti(k,r, s) = Ti(k,s,r),	(4.1)
and if a G Z is such that gcd(2k, a) = 1, then
Ti(k, ar, as) = Ti(k, r, s).
Lemma 4.4. Let k be an odd integer, k > 1, and let r* and X(k) be as in Definition 4.1. Then the graph X(k) is vertex-transitive.
Proof. Recall that X(k) = T1(k,r*, 1). Define $ as the mapping given by:
ui ^ Wi-r*+2, wi ^ Vi-2r*+2, Vi ^ «¿-r*+2 if i is even; Ui ^ Vi+r*-2, Vi ^ wi+2r* —2, Wi ^ ui+r* —2 if i is odd.
That $ is indeed an automorphism follows from the fact that k is odd, r* is even and the congruence k + 3 — 2r* = 0 holds. Since $ transitively permutes the three (p)-orbits U, V and W, the group (p, $) acts transitively on the vertices of T1(k,r*, 1).	□
Lemma 4.5. For k > 1, X(k) has arc-type 2+1.
Proof. Let G be the full automorphism group of X(k) and consider the automorphism p interchanging ui with u—i and vi with w—i, i G Z2k. Note that p is an element of Gu0, the stabiliser of u0. Moreover, p fixes uk but interchanges v0 with w0. This is, p fixes one of the neighbours of u0 while interchanging the remaining two. This implies that the arc-type of X(k) is either 3, when X(k) is arc-transitive, or 2+1. However, there are no arc-transitive graphs of Type 1. The result follows.	□
Remark 4.6. The automorphism given in the proof above is an automorphism of r = T1(k, r, s), from which we see that if r is not vertex-transitive, then V U W is a vertex orbit under its full automorphism group Aut(r). Then r must have two vertex orbits: U and V U W. This shows that item (2) of Theorem 4.2 holds.
Now, recall that r is connected and equals T1(k, r, s), for some k > 9, r,s G Z2k. We may also assume that r is vertex-transitive, however, for some of the results in this section vertex-transitivity is not needed. When possible, we will not assume the graph to be vertex-transitive, but rather only to have some weaker form of symmetry, that we will define in the following paragraphs.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
9
A simple graph r is said to be c-vertex-regular, for some c > 3, if there are the same number of c-cycles through every vertex of r.
For an edge e of r and a positive integer c denote by ec(e) the number of c-cycles that pass through e. For a vertex v of r, let {ei, e2, e3} be the set of edges incident to v ordered in such a way that ec(e1) < ec(e2) < ec(e3). The triplet (ec(e1), ec(e2), ec(e3)) is then called the c-signature of v. If for c > 3 all vertices in r have the same c-signature, then we say r is c-cycle-regular and the signature of r is the signature of any of its vertices. Note that for every c > 3, a vertex-transitive graph is necessarily c-cycle-regular, and every c-cycle-regular graph is c-vertex-regular.
If c equals the girth of the graph, then following [19], a c-cycle-regular graph will be called girth-regular.
Lemma 4.7. If r is 4-vertex-regular, then neither r nor s equals k.
Proof. Suppose r = k. Since r has no parallel edges, we see that s = k. Observe that (u0, v0, wr, ur) and (u0, w0, v_r, u_r) are the only 4 cycles of r through u0.
Meanwhile, there exists a unique 4-cycle through v0, namely (v0, wr, ur, u0), which contradicts r being 4-vertex-regular. Hence r = k, and since T1 (k, s, r) = T1 (k, r, s) (see Equation (4.1)), this also shows that s = k.	□
For the sake of simplicity denote a dart in A1 starting at vertex a, pointing to vertex b and having voltage x by (ab)x. Recall that a walk in A1 is a sequence of darts (x1, x2,..., xn), for instance ((vw)r, (wu)0, (uu)k) is a walk of length 3. However, since r is a simple graph a walk in r will be denoted as a sequence of vertices, as it is normally done.
Lemma 4.8. If r is 8-cycle-regular, then neither r nor s equals 0.
Proof. Suppose r = 0. Since r has no parallel edges, we see that s = 0. Suppose there is an 8-cycle C in r. Such a cycle, when projected to A1, yields a reduced closed walk w in A1 whose Z1-voltage is 0. Note that w cannot trace three darts with voltage 0 consecutively, as this would lift into a 3-cycle contained in C. This implies w necessarily visits the dart (vw)s or its inverse at least once. Furthermore, since gcd(k, s) = 1 and 8 < 9 < k, w must trace (wv)_s as many times as it does (vw)s. By observing Figure 4, the reader can see that if w traces the dart (vw)s, then it must also trace the semi-edge (uu)k before tracing (wv)_s, as w cannot trace three consecutive darts with voltage 0. Since w has net voltage 0, it necessarily traces (uu)k an even number of times. Moreover, w must trace a dart in {(uv)0, (vu)0, (uw)0, (wu)0} immediately before and immediately after tracing (uu)k. Hence, w must visit the set {(vw)s, (wv)_s} at least twice; the semi-edge (uu)k at least twice; and the set {(uv)0, (vu)0, (uw)0, (wu)0} at least 4 times. This already amounts to 8 darts, none of which is (vw)r or its inverse. Therefore, no 8-cycle in r visits an R-edge. However, for X = R there is at least one 8-cycle through every X-edge, as (u0, v0, ws, us, us+fc,ws+fc,vfc,ufc) and (u0,w0, v_s,u_s,ufc_s, vfc_s,wfc,ufc) are 8-cycles in r. This contradicts our hypothesis of r being 8-cycle-regular. The proof when s = 0 is analogous.	□
Now, observe that (u0, uk, vk, wk+r, uk+r, ur, wr, v0, u0) is a cycle of length 8 in r starting at u0. In what follows we will study the 8-cycle structure of r to determine conditions for vertex-transitivity. Recall that each 8-cycle in r quotients down into a closed walk
34
Ars Math. Contemp. 18 (2020) 10-49
of length 8 having net voltage 0 in Ai. We can thus, provided we are careful, determine how many 8-cycles pass through any given vertex of r by counting closed walks of length 8 and net voltage 0 in the quotient A1. Note that only closed walks that are reduced will lift into cycles of r. Therefore, we may safely ignore non-reduced walks and focus our attention exclusively on reduced ones. Define Wg as the set of all reduced closed walks of length 8 in A1.
Every element of Wg having net voltage 0 lifts into a closed walk of length 8 in r. In principle, the latter walk might not be a cycle of r. However, we will show that this never happens in our particular case. For this, it suffices to show that r does not admit cycles of length 4 or smaller, as any closed walk of length 8 that is not a cycle is a union of smaller cycles, one of which will have length smaller or equal to 4.
Lemma 4.9. r has girth at least 5.
Proof. Suppose r has a 3-cycle. Since r is vertex-transitive, this would mean that there is a reduced closed walk with net voltage 0 of length 3 in A1 that visits u. From Figure 4 we get that such a closed walk must be either ((uw)0, (vw)r, (wu)0), ((uw)o, (vw)s, (wu)0) or one of their inverses. This would imply that either r = 0 or s = 0, a contradiction. Similarly, the existence of 4-cycles in r would imply there is a closed walk with net voltage 0 of length 4 visiting u. The only such walks are
((uv)o, («w)r , (wu)o, (uu)k )),	((uu)k, (uv)o, («w)r , (wu)o),
((uv)o, («w)„ (wu)o, (uu)k)),	((uv)o, (vw)s, (wu)o, (uu)fc))
and their inverses. In all eight cases, we have that r = k or s = k, contradicting Lemma 4.7.
□
Now, let N be the set of the net voltages of walks in Wg, expressed as linear combinations of k, r and s, where we view r and s as indeterminants over Z2k. For instance, the closed walk ((uv)0, (vw)r, (wv)_s, (vw)r, (wu)0, (uv)0, (»w)r, (wu)0) has net voltage 3r - s. For an element v G N, let W(v) be the set of walks in W with net voltage v and for a vertex x of A1, let Wf (v) be the set of walks in W(v) starting at x.
For each v G N, we have computed the number of elements in Wg (v) and in Wg (v). The result is displayed in Table 2. Notice that, if u G Wg(v), then u 1 G Wf (—v). This means u has voltage 0 if and only if u-1 does too. For this reason, and since we are interested in walks with net voltage 0, we have grouped walks with net voltage v along with their inverses having net voltage — v. This computation is straightforward but somewhat lengthy. For this reason and to avoid human error, we have done it with the help of a computer programme written in SageMath [21].
From the first Row of Table 2 we know that there are always 12 walks starting at u in Wg that have net voltage 0, regardless of the values of r and s. Similarly, there are always 10 such walks starting at v. Since r is vertex-transitive, the number of walks in Wg having net voltage 0 (after evaluating r and s in Z2k) starting at u and those starting at v must be the same. It follows that, for some v G N with | Wg (v)| > |Wg (v)|, the equation v = 0 (mod 2k) holds when we evaluate r and s in Z2k. We thus see that at least one expression in VIII-XIII is congruent to 0 modulo 2k. In fact, if r is vertex-transitive, then at most one of these expressions can be congruent to 0.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants	11
Table 2: Net voltages of closed walks of length 8 in Ai.
Label	Net voltage	Starting at u	Starting at v
I	0	12	10
II	±(2r)	8	8
III	±(2s)	8	8
IV	±(r + s)	8	4
V	±(r — s)	8	4
VI	±(k + 2r — s)	12	10
VII	±(k + 2s — r)	12	10
VIII	±(k + 3r — 2s)	4	6
IX	±(k + 3s — 2r)	4	6
X	±(3r — s)	4	6
XI	±(3s — r)	4	6
XII	±(2r — 2s)	4	6
XIII	±(4r — 4s)	0	2
Lemma 4.10. If r is 4-vertex-regular and 8-cycle-regular, then exactly one of the following equations modulo 2k holds:
3s	— 2r + k = 0,	(4.2)
3r	— 2s + k = 0,	(4.3)
	3r — s = 0,	(4.4)
	3s — r = 0,	(4.5)
	4r — 4s = 0.	(4.6)
Proof. We will slightly abuse notation and, for a label x € {I, II,..., XIII}, we will refer by x to the congruence equation modulo 2k obtained by making the expression labelled x in Table 2 congruent to 0. For instance, the equation 2r = 0 will be referred to as II.
First note that if II or III holds then r = k or s = k, contradicting Lemma 4.7. If V holds then (v0, wr, v0) is a 2-cycle in r, which is not possible. Similarly, XII implies the existence of a 4-cycle in r, contradicting Lemma 4.9. Now, if XIII holds, then either 2r — 2s = 0, which is not possible, or 2r — 2s + k = 0, which gives Equation (4.6).
If VI holds, then neither X nor XI can hold as this would imply 2r — 2s = 0 (subtracting IV from X or from XI, respectively). Therefore, IV excludes X and XI. If IV and I are the only equations to hold, we would have 6 more elements of W8 through u than through v. This means that if IV holds then necessarily VII, IX and XII also hold. However, XII implies 2r — 2s + k = 0 and subtracting this from VIII we get r = 0, in contradiction with Lemma 4.8. Hence, VII, IX and XII cannot all hold at the same time and so IV can never hold.
Suppose VI holds, then one of the equations in {VIII, IX, X, XI, XIII} must also hold. Note that VI and VIII imply III; VI and IX imply V; VI and X imply r = k; VI and XIII imply s = k. Therefore, by Lemma 4.7, only XI can hold. But VI and XI imply VII, and so we would have 40 elements of W8 starting at u but only 36 starting at v. This would contradict r being 8-cycle-regular. Thus VI cannot hold. An analogous reasoning, where the roles of r and s are interchanged, shows that VII cannot hold. We have shown that
34
Ars Math. Contemp. 18 (2020) 12-49
the only equations that can hold are in {VIII, IX, X, XI, XIII}. However, if two or more of these equations hold, then we would have more elements of W8 through v than we would have through u. It follows that exactly one equation in {VIII, IX, X, XI, XIII} holds. □
Lemma 4.10 tells us, for each of the 5 possible equations, exactly which walks in W8 will lift to 8-cycles and so we can count exactly how many 8-cycles pass through a given vertex or edge of r. For instance, if 3s — 2r + k = 0, then there are 16 walks in W8 through u that will lift to an 8-cycle (see Table 2). Since a closed walk in W8 and its inverse lift to the same cycle in r, we see that there are 8 cycles of length 8 through every vertex in r. Moreover, there are exactly 5 cycles of length 8 through every edge of type R or 0 while there are 6 such cycles through each edge of type K or S. It follows that the 8-signature of a vertex x of r is (5,5,6) whenever 3s — 2r + k = 0 and thus, in this case, r is 8-cycle-regular with 8-signature (5,5, 6). Table 3 shows the number of 8-cycles through each vertex and through each edge, depending on its type, for each of the 5 cases described in Lemma 4.10.
Table 3: Number of 8-cycles through each edge-type of T1(k, r, s).
Congruence	0-edge	R-edge	S-edge	K-edge	8-signature
3s — 2r + k	5	5	6	6	(5, 5, 6)
3r — rs + k	5	6	5	6	(5, 5, 6)
3r — s	6	6	4	4	(4, 6, 6)
3s — r	6	4	6	4	(4, 6, 6)
4r — 4s	4	4	4	4	(4, 4,4)
We will now show that Equations (4.4), (4.5) and (4.6) cannot hold when r is vertex-transitive. This will be proved in Lemmas 4.12, 4.13 and 4.14. But first we need to show a result about the subgraph induced by the 0- and R-edges.
Recall that that r = T1 (k, r, s) with k > 9 and that it is connected. Henceforth we also assume that r is vertex-transitive. Denote by r0,R the subgraph that results from deleting the edges of type S and K from r. Equivalently, r0 ,R is the subgraph induced by 0 - and R-edges. We see that To,r is 2-valent and that it has gcd(2k, r) connected components, each of which is a cycle of length 6k/ gcd(2k, r).
Since r0 ,R only has edges of type 0 and R, any two vertices in the same connected components must have indices that differ in a multiple of r. It is not hard to see that, indeed, each connected component consist precisely of all those vertices whose indices are congruent modulo gcd(2k, r). We now prove an auxiliary result that will be used both in the case where Equation (4.4) as well as in the case where Equation (4.2) or Equation (4.3) holds.
Suppose that no automorphism of r maps an S-edge to a 0-edge. Since r is vertex-transitive, there is an automorphism that maps a vertex from V to a vertex in U. Such an automorphism then maps an S-edge to a K-edge. Since all S-edges as well as all the K-edges are in the same orbit, this then implies that ES U EK forms a single edge-orbit
of Aut(r).
Lemma 4.11. Suppose that no automorphism of r maps an S-edge to a 0-edge, then r0 ,R is disconnected, and the set of connected components induce a block system for the vertex-set of r.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
13
Proof. By the discussion above the lemma, ES U EK forms a single edge-orbit in r. Now note that Aut(T) also acts as a group of automorphism on r0,R and that this action is transitive, since the edges removed consist of an edge-orbit of r. It follows that connected components of r0 ,R form a block system for the vertex set of r. Now, suppose r0 ,R consists of a single cycle of length 6k, (w0, u0, v0, wr, ur, vr,..., v(2k_i)r). Notice that the vertex antipodal to u0 in this cycle is ukr which is the same as uk, as r is odd. We see that edges of type K in r join vertices that are antipodal in r0,R, while S-edges do not. Since this 6k-cycle is a block of imprimitivity, K-edges can only be mapped into K-edges and thus U is an orbit of Aut(r), contradicting the assumption that r is vertex-transitive. Hence, r0 ,R is disconnected.	□
Lemma 4.12. If 3r — s = 0 (mod 2k), k > 9, then T1(k, r, s) is not vertex-transitive.
Proof. Let r = T1(k, r, s) where 3r — s = 0 (mod 2k). A computer assisted counting shows that S-edges and K-edge have exactly 4 distinct 8-cycles passing through them, while 0- and R-edges have 6 such cycles (see Table 3). It follows that any automorphism sending a vertex u G U to a vertex v G V must necessarily map the K-edge incident to u into the S-edge incident to v. Thus ES U EK is an orbit of edges under the action of Aut(r).
Since we are assuming that 3r — s = 0 we get that any number dividing k and r must also divide s, but since gcd(k, r, s) = 1, we have that gcd(k, r) = 1 and then gcd(2k, r) G {1, 2}. In light of Lemma 4.11, r0,R is disconnected, implying gcd(2k, r) = 1 and therefore gcd(2k, r) = 2. From the congruence 3r — s = 0 we also get that r and s must have the same parity thus making s even and k odd. Recall that each connected component of r0,R consists of all the vertices whose indices are congruent modulo gcd(2k, r), so r0,R has two connected components: one containing all the vertices with even index, and the other containing those with odd index. Since s is even and k is odd, S-edges in r join vertices with same parity, while K-edges join vertices with distinct parity. We know that each of the two connected components of r0 is a block of imprimitivity of r, an so any automorphism of r must either preserve the parity of all indices, or of none at all. It follows that no automorphism can send S-edges into K-edges, and therefore no automorphism can send a vertex in V to a vertex in U. We conclude r cannot be vertex-transitive.	□
Lemma 4.13. If 3s — r = 0 (mod 2k), k > 9, then T1(k, r, s) is not vertex-transitive.
Proof. Set r = T1(k, r, s) and r' = T1(k, r', s'), where r' = s and s' = r. Notice that the triplet (k, r', s') satisfies Equation (4.4) and so, by Lemma 4.12, r' cannot be vertex-transitive. By observation (4.1), r = r'. Therefore r is not vertex-transitive.	□
Lemma 4.14. If 4r — 4s = 0 (mod 2k), k > 9, then T1 (k, r, s) is not vertex-transitive.
Proof. Let r = T\ (k, r, s), with 4r — 4s = 0 (mod 2k) and k > 9. From the congruence 4r — 4s = 0, we see that either 2r — 2s = 0 or 2r — 2s + k = 0, but the former contradicts Lemma 4.9. Hence 2r — 2s + k = 0 and the closed walk ((uv)0, (vw)r, (wv)_s, (vw)r, (wv)_s, (vu)0, (uu)k) in A1 lifts to a 7-cycle in r. We will show that r cannot be 7-vertex-regular. Following a similar procedure as the one used to obtain Table 2, we have counted all closed walks of length 7 in A1 starting at u and those starting at v, and we have computed their net voltage. The result is displayed in Table 4.
It is plain to see that if, in addition to I, any one of the voltages in Rows III - VI is congruent to 0, then either r = 0, r = k, s = 0 or s = k, contradicting Lemmas 4.7 or 4.8.
34	Ars Math. Contemp. 18 (2020) 14-49
Table 4: Net voltages of closed walks of length 7 in Ai.
Label	Net voltage	Starting at u	Starting at v
I	±(k + 2r — 2s)	8	10
II	±(k + r + s)	12	8
III	±(k + 2r)	6	4
IV	±(k + 2s)	6	4
V	±(3r — 2s)	2	6
VI	±(3s — 2r)	2	6
We see that only the voltages in Row I or II can hold, and thus r is not 7-vertex-regular and hence cannot be vertex-transitive.	□
In what follow we deal with the case where Equation (4.2) holds, that is, when 3s -2r + k = 0 (mod 2k) and k > 9. From Table 3 we see that S-edges and K-edge have exactly 6 distinct 8-cycles passing through them, while 0- and R-edges have only 5. In particular, no automorphism of r maps an S-edge to a 0-edge, implying that ES U EK is an edge-orbit of r (see the discussion above Lemma 4.11).
Lemma 4.15. Suppose that 3s — 2r + k = 0 (mod 2k), k > 9. If e is an edge in EK U ES, then the endpoints of e belong to different connected components of r0,R.
Proof. Suppose a K-edge e has both of its endpoints in the same connected component, c , of r o,r. Then, because r is vertex-transitive and C is a block of imprimitivity, both of the endpoints of any K-edge must belong to the same connected component of r0 ,R. This means that the subgraph induced by 0-edges, R-edges and K-edges is disconnected. Recall that K-edges and S-edges belong to a single edge-orbit in r and thus, for every S-edge, e', there exists ^ G Aut(r) such ^(e) = e'. Since ^ also acts as an automorphism on r0,R, it follows that the endpoints of ^(e) are contained in the component ^(C), thus making r a disconnected graph, which is a contradiction.	□
Lemma 4.16. Suppose that 3s — 2r + k = 0 (mod 2k), k > 9. Then the subgraph r0,R has an even number of connected components.
Proof. Let e be a K-edge whose endpoints are in two different connected components C1 and C2. Let pr G Aut(r) be an "r-fold" rotation. That is, pr adds r to the index of every vertex. It is plain to see that pr fixes the connected components of r0 ,R set-wise and that it send K-edges into K-edges. Moreover, since it is transitive on U n C1, we have that all K-edges having an endpoint in C1 will have the other endpoint in C2. Hence K-edges "pair up" connected components of r0,R. The result follows.	□
Proposition 4.17. If T1(k, r, s) is connectedandvertex-transitive, thenthe following statements (or the analogous three statements obtained by interchagning r and s) hold:
(1)	3s — 2r + k = 0 (mod 2k)
(2)	k and s are odd and gcd(k, s) = 1
(3) r is even and gcd(k,r) = {1, 3}.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
15
Proof. First, note that item (1) follows from the combination of Lemma 4.10 and Lemmas 4.12,4.13 and 4.14.
We will continue by proving (3). Set d = gcd(k, r), so that r = dr' and k = dk' for some integers k' and r'. Since 3s — 2r + k = 0 (mod 2k), we see that, for some odd integer a:
3s = d(ak' + 2r').
By connectedness, gcd(k, r, s) = 1, and hence gcd(d, s) = 1 implying that d divides 3. Hence d = gcd(k, r) G {1,3}. Moreover, since r0,R has gcd(2k, r) connected components and this number must be even by Lemma 4.16, we see that gcd(2k, r) G {2,6}, and therefore r is even.
Now, from the congruence 3s — 2r + k = 0 (mod 2k) we see that s and k are either both even, or both odd. Since gcd(2k, r, s) = 1 and r is even, s must necessarily be odd and then k is also odd. Set d' := gcd(k, s) so that s = d's' and k = d'k' for some integers s' and k'. Again, from Equation (4.2) we obtain
2r = d'(ak' + 3s')
for some odd integer a. Thus d' G {1, 2}, but since s is odd, we see that gcd(k, s) = 1. This proves item (2) and completes the proof.	□
Remark 4.18. Conditions (1)-(3) (or their analogues) in Proposition 4.17 are also sufficient to prove vertex-transitivity of a connected graph Ti(k, r, s). This will be shown after the proof on Lemma 4.20. Moreover, observe that if k and s satisfy condition (2) of Lemma 4.17, then gcd(2k, 1) = 1 and Ti(k, r, s) is isomorphic to Ti(k, rs-i, 1) where s-i is the multiplicative inverse of s in Z2k. Hence, in what follows we may assume that s = 1.
Lemma 4.19. Let k be an odd number and set s = 1. There exists a unique element r G Z2k such that conditions (1) and (3) of Proposition 4.17 are satisfied. This unique r equals r* from Definition 4.1.
Proof. Suppose that such r exists. From condition (1) of Lemma 4.19, we get r = (3 — ak)/2 for some odd integer a. Since r must be a positive integer smaller than 2k, it follows that a G { — 1, —3}. Hence (3 + k)/2 and (3 + 3k)/2 = (3 + k)/2 + k are the only possible candidates for r. Since k is odd, the integers (3 + k)/2 and (3 + k)/2 + k have different parity. Set r to be whichever one of these two expressions is even. Note that any odd number that divides both r and k must divide 3 and that this is true whether r equals (3 + k)/2 or (3 + k) /2 + k. Thus condition (3) of Lemma 4.19 is satisfied and r equals r * from Definition 4.1.	□
We have just proved that once an odd k > 9 is prescribed, then there is at most one graph Ti (k, r, 1) that is connected and vertex-transitive. The following lemma generalizes this to an arbitrary value of s.
Lemma 4.20. Let k > 9 be an odd integer and let Ti(k, r, s) be vertex-transitive. Then
Ti(k,r,s) = X(k).
Proof. Recall that X(k) = Ti(k, r*, 1), where r* is as in Definition 4.1. Since Ti(k, r, s) is connected and vertex-transitive, conditions (1) - (3) of Proposition 4.17 hold. In particular,
34
Ars Math. Contemp. 18 (2020) 16-49
s is relatively prime to 2k. Then we have T1(k,r, s) — T1(k,s 1r, 1), where s 1 is the multiplicative inverse of s in Z2k. It follows by Lemma 4.19 that Ti(k, s 1r, 1) —
T1(k, r*, 1).	□
Notice that in the previous proof vertex-transitivity is only used to ensure that the graph T1(k,r, s) satisfies conditions (1)-(3) of Proposition 4.17, and from there T1(k,r, s) is shown to be isomorphic to T1(k, r*, 1). Since we know from Lemma 4.4 that T1(k, r*, 1) is vertex-transitive, we have that conditions (1) - (3) of Proposition 4.17 are not only necessary, but also sufficient for vertex-transitivity, and thus Proposition 4.17 may be regarded a characterization theorem.
Remark 4.21. For k > 9, X(k) has girth 8. The proof of this fact is straightforward but lengthy and for this reason we decide to omit it. Note as well that X(k) is not a bipartite graph as every connected component of X(k)0,R is a cycle of odd length.
We have now completed the proof of Theorem 4.2. Item (1) follows from Lemmas 4.4 and 4.20 while item (2) follows from Remark 4.6. Now that we have a characterization for vertex-transitivity, we would like to know when a cubic vertex-transitive tricirculant of Type 1 is also a bicirculant. Note that the only cubic vertex-transitive circulants are prisms and Mobius ladders, which have girth 4. It follows from Lemma 4.9 that no cubic vertex-transitive tricirculant of Type 1 is a circulant.
Lemma 4.22. Let r — T1(k, r, s) be connected and vertex-transitive. If 3 { k, then r is a bicirculant.
Proof. Let p: V(r) ^ V(r) be the mapping given by:
ui ^ vi,	vi ^ wi+r,	wi ^ ui	if i is even;
ui ^ wi+k+s, vi ^ ui+k+s, wi ^ vi+k+s-r if i is odd.
It can be readily seen that p is indeed a graph automorphism. Moreover, since r is even and both k and s are odd, p preserves the parity of the index of all vertices. In fact, it is plain to see that p is the product of the following two disjoint permutation cycles and of length 3k:
^0 — (uo, vo, wr ,ur, vr, w2r, u2r ,v2r, . .., u(k- 1)r, v(k-1)r, wo); — (uk ,ws,vk+2s-r ,uk+r, wr+s,vk+2s, uk+2r . . . vk+2s + (k-2)r ).
Hence, r is a bicirculant.	□
Lemma 4.23. If 3 | k, then X(k) is not a bicirculant.
Proof. Suppose X(k) admits a semiregular automorphism p having two orbits, O1 and O2 of size 3k. Following the notation in [17], X(k) must be isomorphic to H(3k, i, j), I(3k, i, j) or F(3k, i) for some i, j e N. Since X(k) is not bipartite, it cannot be isomorphic to H(3k, i,j). Further, if X(k) = F(3k, i) then each of its orbits under p would admit a matching, which is not possible because 3k is odd. Suppose X(k) — I(3k, i, j) for some i, j e N. It is known that vertex-transitive I-graphs are generalized Petersen graphs and as such, one of the two orbits, say O1, consists of a single cycle having, in this case, length 3k. Recall that the connected components of X(k)0,R are blocks of imprimitivity. Since
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
17
gcd(2k, r) = 6, there are 6 such blocks, each of size k. It follows that no two adjacent vertices of O1 are in the same block. On the other hand, it is plain to see that any 2-path in X(k) has at least two vertices in the same block (see Figure 5). We conclude that X(k) cannot be a bicirculant.	□
Figure 5: T1 (9, 6,1). Bold edges correspond to 0- and R-edges.
Corollary 4.24. If T1 (k,r,s) is vertex-transitive with 3 \ k, then T1 (k,r,s) = GP(3k, k + (—1)a) where a G {1, 2} and a = k (mod 3).
Proof. Let T1 (k, r, s) be vertex-transitive and suppose k = 1 (mod 3). Let ^ = be the automorphism described in the proof of Lemma 4.22. We will show that uk is adjacent
to ^(k+1) (uk). Notice that	(uk) = vk+2s-r+ k—ir, but k + 2s — r = r — s so we
may write ^(k+1) (uk) = vr-s+ k-ir. Recall that gcd(2k, 3) = 1 and r is even. From the congruence k + 2r — 3s = 0 we see that:
2r — 3s = 3k, 3r — 3s + r (k — 1) = 3k, r — s + r (k — 1)/3 = k.
So that ^(k+1) (uk) = vk, which is adjacent to uk. The case when k = 2 (mod 3) can be proved with the use of a similar argument.	□
34
Ars Math. Contemp. 18 (2020) 18-49
This completes the proof of Theorem 4.3. Item (1) follows from Lemma 4.22 and Corollary 4.24, while item (2) is proved in Lemma 4.5.
5 Type 2
Let k > 9 be an integer, and let r, s e z2k. Recall that T2 (k, r, s) is the derived graph of A2 with the normalized voltage assignment for z2k shown in Figure 6.
Figure 6: Type 2.
Then, with the same notation as in Section 4,
U = {uo, ui,..., U2k-1}, V = {vo, vi,..., V2k-1} and W = {wo, wi,..., W2k-1}
are the respective fibres of vertices u, v and w in A2. The set of edges of T2 (k, r, s) can be expressed as the union EK u ER u ES u Eo where:
ek = {wiUi+k : i e z2k}, Eo = {uovo : i e z2k} u {uowo : i e z2k}, er = {uiwi+r : i e z2k}, es = {vivi+s : i e z2k}.
Similarly as with Type 1 cubic tricirculants, we see that every cubic tricirculant of Type 2 is isomorphic to T2(k, r, s) for an appropriate choice of k and r, s e z2k.
Definition 5.1. For an odd integer k > 1, let Y(k) = T2(k, 2,1).
Theorem 5.2. Let k > 9 and let r be a connected cubic tricirculant of Type 2 with 6k vertices. Then the following holds:
1.	r is vertex-transitive if and only if it is isomorphic to Y(k) for some odd integer k.
2.	If r is not vertex-transitive, then it has three distinct vertex orbits under its full automorphism group.
The next theorem gives more information about the graph Y(k).
Theorem 5.3. For an odd integer k > 1 the following holds:
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
19
(1)	Y(k) a bicirculant if and only if 3 { k, in which case it is isomorphic to the graph H(6k, 1, ak + 2) where a e {1, 2} and a = k (mod 3) (see [17]).
(2)	Y(k) is the underlying graph of the toroidal map {6,3}a,3 where a = ^ (k — 3).
(3)	Y(k) has arc-type 2+1.
We devote the remainder of this section to proving Theorems 5.2 and 5.3.
Remark 5.4. Note that T2 (k, r, s) and T2 (k, r, —s) are in fact the exact same graph. Then, we can safely assume s < k.
Lemma 5.5. For an odd integer k > 1, Y(k) is vertex-transitive.
Proof. Since Y(k) = T2(k, r, s), it suffices to give an automorphism of T2(k, 2,1) that mixes the sets U, V and W. Let f be the mapping given by:
ui ^ vi+i,	vi ^ ui+i,	wi ^ vi	if i is even;
ui ^ wi+2+k,	vi ^ wi+2,	wi ^ ui+k	if i is odd.
Now consider a vertex ui e U with i even. Observe that f maps ui to vi+i and that the neighbourhood N(ui) := {vi, wi, wi+2} is mapped to {ui+i, vi, vi+2}, which is precisely the neighbourhood of vi+i. That is, f maps the neighbourhood of any vertex ui into the neighbourhood of its image, when i even. The reader can verify the remaining cases and see that f is indeed a graph automorphism.	□
Lemma 5.6. For an odd integer k > 9, Y(k) has arc-type 2+1.
Proof. Let G be the full automorphism group of Y(k), k > 9, and consider the automorphism f interchanging wi with w-i, ui with u-i-2 and vi with v-i-2, i e Z2k. Note that ^ e Gw0 and that it fixes wk while interchanging u0 with u-2. Since no Y(k) with k > 9 is arc-transitive, it follows that its arc-type is 2 + 1.	□
For the rest of this section, let k > 9 be an integer, let r, s e Z2k and suppose r = T2(k, r, s) is vertex-transitive. In what follows we will show that r is isomorphic to Y(k). As with cubic tricirculants of Type 1, the strategy will be to count reduced closed walks in the quotient A2. Observe that the walk ((wu)0, (uw)r, (ww)k, (wu)-r, (uw)0, (ww)k) starting at w is a closed walk of length 6 having net voltage 0, regardless of what r and s evaluate to in Z2k. As was done with graphs of Type 1, we computed all closed walks in A2 along with their net voltages. Again, it would be convenient if closed walks of length 6 with net voltage 0 always lift into 6-cycles. For this it suffices to show that the girth of r is at least 4.
Lemma 5.7. r has no cycles of length 3.
Proof. Suppose to the contrary, that r contains a triangle T. By observing Figure 6 we can see that all three vertices of T belong to V or they belong to U U W. Since r is vertex-transitive, there is at least one triangle through every vertex in W. We can thus assume without loss of generality that all three vertices of T are in U U W. This implies that r = k and further, that there are 2 distinct triangles through every vertex in W: the lifts of ((wu)0, (uw)r, (ww)k) and ((wu)-r, (uw)0, (ww)k). However, since the subgraph induced by V is 2-valent, there is at most one triangle through every vertex in V, contradicting the vertex-transitivity of r.	□
34
Ars Math. Contemp. 18 (2020) 20-49
Note that since r is simple, s = k and if r = k, r would contain a triangle. Thus the following corollary holds.
Corollary 5.8. Neither r nor s equals k.
Now, let W6 be the set of all walks of length 6 in A2 and let N be the set of net voltages of elements of W6, expressed in terms of k, r and s. It follows from Lemma 5.7 that walks in W6 with net voltage 0 will lift into 6-cycles, and not just closed walks. Table 5 shows, for each element n of N, how many closed walks with net voltage n start at each vertex of A2.
Table 5: Net voltages of closed walks of length 6 in A2.
Label	Net voltage	Starting at u	Starting at v	Starting at w
I	0	2	0	4
II	±(k — s)	8	8	8
III	±(k — r — s)	4	4	4
IV	±(k + r — s)	4	4	4
V	±(3r)	2	0	2
VI	±(2r)	2	0	4
VII	±(6s)	0	2	0
VII	±(r — 2s)	4	6	2
IX	±(r + 2s)	4	6	2
From Row I of Table 5 we see that there are at least 4 walks w G W6 starting at w. Therefore, at least one expression from Rows II-IX must be congruent to 0 (mod 2k). However, a careful inspection of Table 5 shows that if neither of the expressions in Rows VIII and IX are congruent to 0 (mod 2k), then there are at least 2 more walks in W6 with net voltage 0 starting at w than there are those starting at v. This means that if r is vertex-transitive, then one of the following two equations modulo 2k hold:
r = 2s,	(5.1)
r = -2s
Suppose Equation (5.1) holds. By Remark 5.4 we can in fact write r = 2s. Then the mapping ^: T2 (k, 2s, s) ^ T2(k, -2s, —s) given by xj ^ x_j, for all x G U U V U W, is a graph isomorphism. But, again by Remark 5.4, T2(k, —2s, —s) = T2(k, —2s, s) so that any graph T2 (k, r, s) with r = 2s is isomorphic to a graph T2 (k, r', s) satisfying r' = —2s. We can therefore limit our analysis to the case when Equation (5.1) holds.
Let r = T2(k, r, s) be connected and vertex-transitive, and suppose r = 2s. Note that any number dividing both k and s must also divide r, and since by connectedness of r gcd(k, r, s) = 1 we see that gcd(k, s) = 1 and gcd(2k, s) G {1, 2}. We will show that gcd(2k, s) cannot be 2.
Lemma 5.9. If r is vertex-transitive, gcd(2k, s) = 1 and gcd(2k, r) = 2.
Proof. In order to get a contradiction, suppose gcd(2k, s) = 2. Then s is even and k is odd, as gcd(k, s) = 1. Furthermore, the 2-valent subgraph of r induced by the set V is the union of two k-cycles. We will show that these are in fact the only two k-cycles in
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
21
r which will imply that r cannot be vertex-transitive. Suppose there is a k-cycle C' that visits a vertex not in V. Define r[U U W] as the subgraph of r induced by the set U U W. Since r is even and k is odd, it is not difficult to see that r[U U W] is bipartite, with sets {wj : i is even} U {u : i is odd} and {wj : i is odd} U {u : i is even}. Therefore no k-cycle of r is contained in r[U U W]. This means that C' visits at least one vertex in each of sets U, V and W.
Now, C' projects onto a closed walk C in A2 that has net voltage 0. Define xs as the number of times C traces the dart (vv)s minus the number of times it traces (vv)_s, so that xss is the total voltage contributed to C by darts in {(vv)±s}. Define xR similarly, and define xK as the number of times C traces the semi-edge (ww)k. We obtain the following congruence modulo 2k:
XRr + xs s + xk k = 0.
Recall that both r and s are even, making both xRr and xs s even. It follows that xK k is even, but since k is odd, xK must be even, and hence xKk = 0 (mod 2k). We thus have
XRr + xs s = 0
and since r = 2s (mod 2k),
xr2s + xs s = 0, s(2xfl + xs) = 0.
From this, and because gcd(k, s) = 1, we see that 2xR + xs = 0 or 2xR + xs > k. To see that 2xR + xs cannot equal 0, define A as the set of darts in A2 with voltage 0 or r and observe that C must visit A an even number of times. Since C has odd length, C visits
{(vv)±s} U {(ww)k} an odd number of times. Then, since xK is even, xs must be odd. But 2xR is even so 2xR + xs = 0. We thus have
2xr + xs > k.
Now, notice that if C traces the dart (uw)r, then it must immediately trace a dart in {(wu) 0, (ww) k }. This means that C traces a dart in the subgraph of A2 induced by U U W at least 2xR times. Then 2xR + xs < k, since C has length k and it must visit (vu)0 at least once. We thus have k > 2xR + xs > k, a contradiction. The result follows. □
Lemma 5.10. If T2 (k, r, s) is vertex-transitive, k is odd.
Proof. Suppose to the contrary that k is even. Since s is odd, we have sk = k (mod 2k), and thus s(2 • i)k = k. But k is even, so we can rewrite that expression as 2s • | = k. Recall that r = 2 s and then r | = k.
Now, consider the walk of length k + 1 in A2 that starts in w, traces the semi-edge (ww)k once and then traces the 2-path ((wu)r, (uw)0) exactly | times. Note that this walk is closed and has net voltage |r + k = 0. Furthermore, it is easy to see that it lifts into a (k + 1)-cycle in r and that it does not visit any vertex in V.
Since r is vertex-transitive, there must be a (k + 1)-cycle C' through each vertex in V. Note that the subgraph of r induced by V is a single 2k-cycle, and thus C' must visit all three set U, V and W. It follows that C' projects into a walk C of length k + 1 having net voltage 0 and that it visits all three vertices of A2. Furthermore, since k + 1 is odd, the
34
Ars Math. Contemp. 18 (2020) 22-49
number of times C visits {(vv)±s} must be of different parity than the number of times it traces (ww)k. Define xs, xR and xK as in the proof of Lemma 4.16. Hence
XRr + xs s + xk k = 0.
Now, r and k are even, and so xRr and xKk are also even. It follows that xss is even, but since s is odd, ss is necessarily even. This means C visits {(vv)±s} an even number of times. It follows that C traces (ww)k and odd number of times, that is, xK is odd. We thus have
x^r + xs s + k = 0, x^r + xs s = k,
and since r = 2s,
s(2xr + xs) = k.
This implies 2xR + xs > k, as s and k are relatively prime. However, 2xR + xR < k - 1 since C has length k +1 and C visits the set {(vw)0, (uv)oj at least twice. This contradiction arises from the assumption that k is even. We conclude that k is odd. □
Lemma 5.11. For an odd k > 9, if T2 (k, r, s) is vertex-transitive then we have
T2(k,r,s) = Y(k).
Proof. Let T2(k, r, s) be vertex-transitive. Then, by Lemmas 5.10 and 5.9 k is an odd integer, gcd(2k, s) = 1 and r = 2s. Denote by s-1 the multiplicative inverse of s in Z2k. Now, define f as the mapping between T2(k, 2,1) and T2(k, r, s) given by xj I y x®— 1j, for x G U U V U W. It is plain to see that f is the desired isomorphism. Therefore
T2(k, r, s) = T2(k, 2,1) = Y(k).	□
This, together with Lemma 5.5, proves the first claim of Theorem 5.2. We now proceed to show that a tricirculant of Type 2 that is not vertex-transitive must have 3 distinct orbits on vertices.
Lemma 5.12. Let r be a tricirculant of Type 2. If r is not vertex-transitive, then it has 3 distinct vertex orbits.
Proof. We will slightly abuse notation and say r = T2 (k, r, s) for some k G Z and r, s G Z2k. Let f G Aut(r) and let u G U. Suppose that f maps u to some vertex vj g V. Then f must map the neighbourhood of Uj, {vj, Wj, wi+r} to {uj,vj-s,vj+s}, the neighbourhood of vj. It is straightforward to see that f must map a vertex in W to a vertex in V. This is, f "mixes" the set V with the sets U and W implying that r is vertex-transitive, a contradiction. Similarly, if f maps uj to some Wj G W then it must map {vj,wj,wj+r} to {wj+fc,wj,Mj-r}. Thus f maps vj into either U or W contradicting again r not being vertex-transitive. This shows that the set U is a single vertex orbit of r under Aut(r). An analogous argument shows that V is a single vertex orbit and therefore r has three distinct orbits on vertices: U, V and W.	□
The proof of Theorem 5.2 is now complete. In the following paragraphs we will give further details about the structure of a vertex-transitive tricirculant of Type 2. In particular, we will show that Y(k) can be seen as a map on the torus and we will give sufficient and necessary conditions for Y(k) to be a bicirculant. This will prove items (1) and (2) of Theorem 5.3.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
23
Proposition 5.13. Let k > 3 be an odd integer, then Y(k) admits an embedding on the torus with hexagonal faces, yielding a map of type {6, 3}a,3, where a = 1 (k — 3) (see [5] for details about the notation).
Proof. First, notice that vertices in U u W with even index form a cycle of length 2k, C1 = (w0, u0, w2, u2,..., w2k_2, u2k_2). Likewise, vertices in U u W with odd index form a 2k-cycle, C2. The vertices in V form a third cycle of length 2k, C3.
Now, wjwi+k e E for all i e z2k, and i+k has different parity than i. This means each vertex of C1 of the form wi is adjacent, through a K-edge, to a vertex of C2. Further, each vertex of the form ui in C1 is adjacent to a vertex in C3, namely vi. Note that the vertices of C2 that are not adjacent to a vertex of C1 are precisely those of the form ui (with i odd), and that ui vi e E for all odd i. This is, every other vertex in C2 has a neighbour in C3.
Therefore, we can think of Y(k) as three stacked 2k-cycles C1, C2 and C3 where every other vertex of Ci has a neighbour in Ci_1 while each of the remaining vertices has a neighbour in Ci+1, where i ± 1 is computed modulo 3 (see Figure 7 for a detailed example). From here it is clear that T2(k, 2,1) can be embedded on a torus, tessellating it with 3k hexagons. It can be readily verified that this yields the map {6, 3}a,3, where a = 2 (k — 3), following the notation in [5].	□
Figure 7: The graph Y(9). The subgraph induced by bold edges has three connected components that correspond, from bottom to top, to the cycles C, C2 and C3 described in the proof of Proposition 5.13.
Corollary 5.14. For k > 3, Y(k) has girth 6 and is bipartite.
Observe that Y(9) corresponds to the map {6,3}3,3, which is a regular map (see Chapter 8.4 of [5]). It follows that T2 (9,2,1) is arc-transitive, making it one of the four possible cubic arc-transitive tricirculant graphs (called F054A in [10], following Foster's notation).
Lemma 5.15. If k > 1 is an odd integer such that 3 { k, then Y(k) is a bicirculant.
Proof. Consider the mapping ^ defined by:
Ui ^ Wi+2+k,	vi ^ Wj+2,	Wi ^ ui+k	if i is even;
Ui ^ vi+1,	vi ^ Ui+1,	wi ^ vi	if i is odd.
For a vertex ui e U, we have ^ (ui) e U if and only if 3 | l. This is, if we start at U, every third iteration of ^ lands us in U again. Moreover, we have (ui ) = ui+3+k. In general (ui) = ui+31+1k. Hence (ui) = ui if and only if 31 + Ik = 0. If 3 { k, then
34
Ars Math. Contemp. 18 (2020) 24-49
l = k is the smallest value for l that satisfies 3l + Ik = 0. It follows that the orbit of u has size 3k. It is plain to see that the vertices not in this orbit form an orbit of size 3k on their own, namely, the orbit of ui+1. Hence Y(k) is a bicirculant and is isomorphic to the graph H(3k, 1, ak + 2), where a G {1, 2} and a = k (mod 3) (see [17] for details). It is worthwhile to mention that if 3 does divide k, then ^ has 6 orbits of size k.	□
Lemma 5.16. If k > 1 is an odd integer such that 3 | k, then Y(k) is not a bicirculant.
Proof. Let k be an odd integer divisible by 3. To make this proof more succinct, we will assume that Y(k) is not arc-transitive, this is, that k > 9. The graphs Y(3) and Y(9) can be verified to not be bicirculants individually. By Lemma 5.6, Y(K) has arc-type 2 + 1 and the set E' = {uv | i G Z2k} U {w^wk+1 | i G Z2k} is an orbit of edges under the full automorphism group of Y(k). Then each connected component of Y(k) — E' is a block of imprimitivity for Aut(Y(k)). Furthermore Y(k) — E' has three connected components that correspond precisely to the three 2k-cycles Q, i G {1, 2, 3}, in the proof of Proposition 5.13. For convenience, we will relabel the vertices of Y(k) as follows: for each i G {1,2,3}, let V(Q) = {v^- | j G }, where v^- is adjacent to v^--1, v^-+1 and vi+1,j-1. It is straightforward to see that this labelling is always possible.
Now, suppose Y(k) admits a bicirculant automorphism p. Since a p-orbit has size 3k, and every 2k-cycle Q is a block of imprimitivity, p must cyclically permute them. Without loss of generality p(Ci) = Ci+1. Then, p is determined, up to two possibilities, by its action on a single vertex. Indeed, if p(vi,0) = vi+1,a then the two neighbours of vi,0 in Q must be mapped to the neighbours of p(v^,0) in Ci+1. In other words, the set {vi,-1, vi,1} is bijectively mapped to {v^,a-1, vi,a+1} in one of two possible ways, and this completely determines the action of p. In short, for all i G {1, 2, 3} and j G Z2k one of the following holds:
(1)	p(vi,j) = vi+1,j+a,
(2)	p(vi,j) = vi+1 ,-j+a.
If (2) holds, then p3(v^,j) = vi,-j+a and so p6(v^,j) = . This is, p has order 6, which implies that Y(k) has order 12 and hence k = 2, which contradicts k being odd and
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
25
divisible by 3. If (1) holds, then p3(v^-) = v^-+3a and since 3 | k, a vertex v^j can only be mapped to a vertex v1,b by an element of (p) if j = b (mod 3). This implies that p has at least 3 orbits on vertices, contradicting that it is a bicirculant automorphism. The result follows.	□
Theorem 5.3 now follows from Proposition 5.13 and Lemmas 5.6, 5.15 and 5.16. 6 Type 3
Let us begin this section by giving the definition of two well-known families of cubic graphs. For a positive integer k, the prism Pk is the graph of order 2k with vertex set {uo,u1,... , uk-1} U {vo, v1,..., vk-1} and edges of the form uui+1, vvi+1 and uv, where the indices are taken modulo k. The Möbius ladder Mk is the graph with vertex set {uo, u1,..., u2k-1} and edges of the form uui+1 and uui+k, where indices are taken modulo 2k.
Let k > 9 be an integer, and let r e Z2k. Recall that T3 (k, r) is the derived graph of A3 with the normalized voltage assignment for Z2k shown in Figure 9.
o / \o
w
Figure 9: Type 3.
Let U = {uo,U1,... ,U2k-1}, V = {vo, V1,..., V2k-1} and W = {wo, W1, ..., w2k-1} be the respective fibers of vertices u, v and w in A3. It is clear that any cubic tricirculant of Type 3 is isomorphic to T3 (k, r) for some k and r.
Theorem 6.1. If T3 (k, r) is connected, then it is isomorphic to either a prism or a Möbius ladder.
Proof. First, recall that T3(k, r) is connected if and only if gcd(k, r) = 1. Then gcd(2k, r) e {1, 2}, depending on whether r is even or odd.
If r is odd, then the subgraph induced by 0 - and R-edges is a single cycle of length 6k, (wo, uo, vo, wr, ur, vr,..., w2k-r, u2k-r, v2k-r, wo). It is straighforward to see that K-edges join antipodal vertices in this cycle. Hence, in this case T3(k,r) is a Möbius ladder.
If r is even, then the graph induced by 0- and R-edges is the union of two disjoint cycles of length 3k: one consisting of all the vertices with even index, and the other consisting on those with odd index. Observe that K-edges connect these two cycles creating a prism. □
34
Ars Math. Contemp. 18 (2020) 26-49
(a) Ts(9,4)
(b) Ts(9,1)
Figure 10: A prism and a Möbius ladder on 54 vertices.
7 Type 4
Let k be a positive integer, and let r and s be two distinct integers in Z2k. Recall that T4(k,r, s) is the derived graph of A4 with the normalized voltage assignment for Z2k shown in Figure 11. Let U = {u0, u1, ...,u2k-1}, V = {v0 ,v1, ...,v2k-1} and
Figure 11: Type 4.
W = {w0, w1,..., w2k-1} be the respective fibers of vertices u, v and w in A4. Then, the set of edges of T4(k, r, s) can be expressed as the union EK U ER U ES U E0 where:
Ek = {uiUi+k : i G Z2k}, Eo = {uiVi : i G Z2k} U {uiWi : i G Z2k}, Er = {viVi+r : i G Z2k}, Es = {wiWi+s : i G Z2k}.
For X G {0, R, S, K}, edges in EX will be called edges of type X, or simply X-edges. Similarly as with tricirculants of Types 1, 2 and 3, every cubic tricirculant of Type 4 with 6k vertices is isomorphic to T4(k, r, s) for an appropriate choice of r and s.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
27
Remark 7.1. Note that for any k, r and s the following isomorphism holds:
T/j(k, r, s) = T/j(k, —r, s) = T/j(k, r, —s) = T/j(k, s, r).
Theorem 7.2. There are no cubic vertex-transitive tricirculants of Type 4 of order greater or equal to 54.
The rest of this section is devoted to prove Theorem 7.2 as well as to characterise Type 4 tricirculants with 2 and 3 vertex orbits. We will assume henceforth that k > 9 and thus the order of T4(k, r, s) is at least 54.
Lemma 7.3. If T4(k, r, s) is vertex-transitive, then r = s and r = —s.
Proof. Suppose that r = s and consider the graph r := T4(k,r, r), with k > 9 and 1 < r < k — 1. Observe that (v0, vr, ur, wr, w0, u0, v0) is a 6-cycle of r that does not contain any K-edge but does contain edges of all other types. For r to be vertex-transitive, there must be at least one 6-cycle through a K-edge; otherwise K-edges conform a single edge-orbit and thus U is a single vertex-orbit. However, such a cycle would quotient down to a closed walk of length 6 in A4 having voltage 0 and tracing the semi-edge (uu)k. By observing Figure 11 we see that any closed walk of length 6 visiting (uu)k has net voltage k ± 3r. That is, if r is vertex-transitive, then 3r = k (mod 2k). Observe that under these conditions, r is connected if and only if r =1 and thus making k = 3, contradicting that k > 9. This shows that r = s and in view of Remark 7.1, r = —s.	□
Lemma 7.4. Let e be a K-edge of T4(k, r, s) and let a be an integer greater than 4. If C is an cycle of length a containing e then there exists another cycle of length a, C', such that the intersection C n C' contains a 3-path whose middle edge is e.
Proof. Without loss of generality, we can assume e = w0wfc. Define H as the subgraph of r induced by vertices at distance at most one from e, and let C be a k-cycle through e (see Figure 12). Observe that C intersects H in a 3-path, P, whose middle edge is e. Now, let ^ be the mapping that acts by multiplying the index of each vertex by —1; that is ^ maps ui into u-i, vi into v-i, and wi to w-i. Observe that ^ is in fact an automorphism of r. Moreover, ^ fixes each vertex and each edge of H. In particular, it fixes P. Therefore, ^(C) is a k-cycle through e and P lies in the intersection of C and ^(C). To see that ^(C) is different from C, observe that ^ interchanges the two vertices in each of the following sets: {vk+r, vk-r}, {vr, v-r},{wk+s, wk-s} and {ws, w-s} (white vertices in Figure 12). It is clear that C can visit at most one vertex in each of these four sets, and if C visits one vertex in one of these sets, then ^(C) must visit the other.	□
Lemma 7.5. If T4(k,r, s) is vertex-transitive, thenin Z2k one of the equalities (A1) - (A4) below and one of the equalities (B1) - (B4) below hold:
(A1)	k + 2r + s = 0,	(B1)	k + 2s + r = 0,
(A2)	k — 2r + s = 0,	(B2)	k — 2s + r = 0,
(A3) (A4)
r + 3s = 0, r — 3s = 0,
(B3) (B4)
s + 3r = 0, s 3r = 0.
Proof. Suppose T4 (k, r, s) is vertex-transitive. We will first show that one of the equalities (A1) - (A4) holds in Z2k. The rest of the lemma will follow from the fact that T4 (k, r, s) =
34
Ars Math. Contemp. 18 (2020) 28-49
Figure 12: Neighbourhood of u0uk. The subgraph H shown in solid edges and vertices.
T4(k,s,r). Since T4(k,r, s) is vertex-transitive, the edge-neighbourhood of any vertex in U can be mapped by an automorphism to the edge-neighbourhood of any vertex in V. In particular, either there exists an automorphism mapping the K-edge u0 uk to the 0 -edge u0v0 or there is an automorphism mapping u0uk to the R-edge v0vr. Therefore, the property described in Lemma 7.4 should also hold for u0v0 or for v0vr (or possibly both). We will see what this means in terms of k, r and s.
Suppose that the property described in Lemma 7.4 holds for u0v0. Observe that there is an 8-cycle C = (u0,v0,v-r,u-r,u^-r,v^-r, v& , ,u0) through u0v0 (see Figure 13). Then there must be another 8-cycle C' whose intersection with C contains the 3-path (v-r,v0,u0 ,uk), but no 4-path containing this 3-path. This in turns implies that some vertex in {v-3r, u-2r} is adjacent to a vertex in {wk-s }. Since no vertex in V is adjacent to a vertex in W, we have that either u-2rwk-s e E or u-2rwk+s G E. This implies 2r = k + s or 2r = k — s, and so (A1) or (A2) holds.
u0 v0
Figure 13: A part of the graph T4 (k, r, s) containing u0v0.
If, on the other hand, the property described in Lemma 7.4 holds for v0vr, then one vertex in {wr+s, wr-s} must be adjacent to a vertex in {ws, w-s} (see Figure 14), implying
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
29
that one of the following expressions must be equal to 0 in Z2k: r + 3s, r + s, r — 3s, r — s. However, in view of Lemma 7.3, r + s = 0 and r — s = 0. Hence (A3) or (A4) holds. □
vr
Figure 14: A subgraph containing v0vr.
We are now ready to prove Theorem 7.2. Let k > 9 be an integer and suppose T4(k, r, s) is vertex-transitive. Then, by Lemma 7.5, one of the equalities (A1)-(A4) and one of the equalities (B1)-(B4) must hold. If, for instance both (A1) and (B1) hold, then by adding them we see that r = — s, which contradicts Lemma 7.3. Similarly, we get that r ± s if both equalities in any of the following pair hold: (A1) and (B2), (A2) and (B2), (A3) and (B3). If (A1) and (B4), or (A2) and (B4) hold, then k = r, which contradicts the simplicity of r. If (A1) and (B3), (A2) and (B3), or (A3) and (B4) hold, then either k = 5 or gcd(k, r, s) = 1. It is readily seen that we get a contradiction in each of the 16 possible cases that arise from Lemma 7.5. We conclude that a connected T4(k, r, s) cannot be vertex-transitive if k > 9.
Lemma 7.6. Let k > 9 and T4(k,r, s) be connected. Let a = gcd(2k,r), R = r/a, S = s/a. Then T4(k,r, s) has two orbits on vertices if and only if a e {1, 2} and (SR-1 )2 = ±1 (mod 2k/a), where R-1 is the multiplicative inverse of R modulo 2k/a (or the equivalent statement obtained from interchaging r and s).
Proof. For a graph r of Type 4, let r* be the graph obtained from r by deleting all vertices in U (along with the edges incident to them) and making v adjacent to w, i e Z2k. Then r* is isomorphic to the bicirculant I-graph I(2k, r, s) of order 4k. Moreover, each automorphism ^ e Aut(r) induces an automorphism e Aut(r*) in a natural way. Denote by Aut* (r*) the group of all automorphism of r* induced by an automorphism of r.
Now suppose r has two orbits on vertices. Since K-edges can only be mapped to K-edges, these two orbits must necessarily be U and V U W. This is, Aut(r) acts transitively on V U W and so Aut* (r*) is transitive on the vertices of r*.
If r* = I(2k, r, s) is connected then it must be a vertex-transitive generalised Petersen graph [17]. This is, without loss of generality, the graph induced by V is a 2k-cycle, and thus gcd(2k,r) = 1. Let r-1 be the multiplicative inverse of r modulo 2k and let A = T4(k, 1, sr-1). Then A = r = T4(k, r, s). Moreover, A* is isomorphic to the generalised Petersen graph GP(2k,sr-1), and since it is vertex-transitive we have (sr-1 )2 = ±1 (mod 2k) [8].
34
Ars Math. Contemp. 18 (2020) 30-49
If r* = I(2k, r, s) is disconnected, then it must have two connected components. Indeed, since r is connected we have gcd(2k, k, r, s) = 1, but I(2k, r, s) is disconnected if and only if gcd(2k, r, s) = 1. Then necessarily gcd(2k, r, s) = 2 and both r and s are even while k is odd. Each connected component is isomorphic to I(k, r/2, s/2). An analogous argument as the one used in the connected case shows that gcd(k, r/2) = 1, (and since k is odd, gcd(k, r) = 1 and gcd(2k,r) = 2) and (SR-1)2 = ((s/2)(r/2)-1)2 = ±1 (mod k).
For the reverse implication let k > 9 and r, s G Z2k. Suppose that a = gcd(2k, r) G {1, 2} and (SR-1)2 = ±1 (mod 2k/a), where R-1 is the multiplicative inverse of R modulo 2k/a. Let r = T4(k, r, s). Define ^: r ^ r as follows:
Ui ^ U(SR-I)i, Vi ^ W(SR-I)i, Wi ^ V(SR-I)i for all i G Z2k.
Observe that SR-1r = s (mod 2k) and sSR-1 = ±r (mod 2k). From here, it is routine to check that ^ is an automorphism of r. We conclude that V UW is a vertex orbit of r. □
ORCID iDs
Primož Potočnik © https://orcid.org/0000-0001-5028-3545 Micael Toledo © https://orcid.org/0000-0002-9531-3506
References
[1]	I. Z. Bouwer (ed.), The Foster Census: R. M. Foster's Census of Connected Symmetric Trivalent Graphs, Charles Babbage Research Centre, Winnipeg, Canada, 1988.
[2]	P. Cameron, J. Sheehan and P. Spiga, Semiregular automorphisms of vertex-transitive cubic graphs, European J. Combin. 27 (2006), 924-930, doi:10.1016/j.ejc.2005.04.008.
[3]	P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Marušic and L. A. Nowitz, Transitive permutation groups without semiregular subgroups, J. London Math. Soc. 66 (2002), 325-333, doi:10.1112/s0024610702003484.
[4]	M. D. E. Conder, T. Pisanski and A. Žitnik, Vertex-transitive graphs and their arc-types, Ars Math. Contemp. 12 (2017), 383-413, doi:10.26493/1855-3974.1146.f96.
[5]	H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups, volume 14 of Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, Berlin-New York, 4th edition, 1980.
[6]	J. Folkman, Regular line-symmetric graphs, J. Comb. Theory 3 (1967), 215-232, doi:10.1016/ s0021-9800(67)80069-3.
[7]	B. Frelih and K. Kutnar, Classification of cubic symmetric tetracirculants and pentacirculants, European J. Combin. 34 (2013), 169-194, doi:10.1016/j.ejc.2012.08.005.
[8]	R. Frucht, J. E. Graver and M. E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambr. Philos. Soc. 70 (1971), 211-218, doi:10.1017/s0305004100049811.
[9]	M. Giudici, I. Kovdcs, C. H. Li and G. Verret, Cubic arc-transitive k-multicirculants, J. Comb. Theory Ser. B 125 (2017), 80-94, doi:10.1016/j.jctb.2017.03.001.
[10]	I. Kovdcs, K. Kutnar, D. Marušic and S. Wilson, Classification of cubic symmetric tricirculants, Electron. J. Combin. 19 (2012), #P24 (14 pages), doi:10.37236/2371.
[11]	A. Malnic, D. Marušic and P. Potocnik, Elementary abelian covers of graphs, J. Algebraic Combin. 20 (2004), 71-97, doi:10.1023/b:jaco.0000047294.42633.25.
P. Potočnik and M. Toledo: Classification of cubic vertex-transitive tricirculants
31
[12]	A. Malnic, R. Nedela and M. Skoviera, Lifting graph automorphisms by voltage assignments, European J. Combin. 21 (2000), 927-947, doi:10.1006/eujc.2000.0390.
[13]	D. Marusic, On vertex symmetric digraphs, Discrete Math. 36 (1981), 69-81, doi:10.1016/ 0012- 365x(81)90174- 6.
[14]	D. Marusic, Semiregular automorphisms in vertex-transitive graphs with a solvable group of automorphisms, Ars Math. Contemp. 13 (2017), 461-468, doi:10.26493/1855-3974.1486.a33.
[15]	D. Marusic, Semiregular automorphisms in vertex-transitive graphs of order 3p2, Electron. J. Combin. 25 (2018), #P2.25 (10 pages), doi:10.37236/7499.
[16]	D. Marusic and R. Scapellato, Permutation groups, vertex-transitive digraphs and semiregular automorphisms, European J. Combin. 19 (1998), 707-712, doi:10.1006/eujc.1997.0192.
[17]	T. Pisanski, A classification of cubic bicirculants, Discrete Math. 307 (2007), 567-578, doi: 10.1016/j.disc.2005.09.053.
[18]	P. Potocnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J. Symbolic Comput. 50 (2013), 465-477, doi:10.1016/j.jsc.2012.09.002.
[19]	P. Potocnik and J. Vidali, Girth-regular graphs, Ars Math. Contemp. 17 (2019), 349-368, doi: 10.26493/1855-3974.1684.b0d.
[20]	P. Spiga, Semiregular elements in cubic vertex-transitive graphs and the restricted Burn-side problem, Math. Proc. Cambridge Philos. Soc. 157 (2014), 45-61, doi:10.1017/ s0305004114000188.
[21]	The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.3), 2018, https://www.sagemath.org/.
[22]	W. T. Tutte, Connectivity in Graphs, University of Toronto Press, Toronto, 1966, http:// www.jstor.org/stable/10.3138/j-ctvfrxhc8.