ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 15 (2018) 1-17 https://doi.org/10.26493/1855-3974.1007.3ec (Also available at http://amc-journal.eu) Linking rings structures and semisymmetric graphs: Combinatorial constructions Primoz Potocnik * Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia affiliated also with: IMFM, Jadranska 19, SI-1000 Ljubljana, Slovenia Stephen E. Wilson Department of Mathematics and Statistics, Northern Arizona University, Box 5717, Flagstaff, AZ 86011, USA affiliated also with: FAMNIT, University ofPrimorska, Glagoljaska 8, SI-6000 Koper, Slovenia Received 30 December 2015, accepted 27 July 2017, published online 2 November 2017 This paper considers combinatorial methods of constructing LR structures: two isolated constructions, RC and SoP, two closely related constructions, CS(T, B, 0) and CS(T, B, 1) using cycle decompositions of tetravalent graphs, a generalization of those, CS(T, B, k) for k > 2, and finally a construction LDCS relating to cycle decompositions of graphs of higher even valence. This last construction is used to classify all LR structures of types {3, *} or {4, *}. Keywords: Graph, automorphism group, symmetry, locally arc-transitive graph, semisymmetric graph, cycle structure, linking ring structure. Math. Subj. Class.: 20B25, 05E18 1 Introduction 1.1 History An LR structure is a finite, simple, connected, tetravalent vertex-transitive graph together with a decomposition of its edge-set into cycles that satisfies certain symmetry conditions * Supported in part by Slovenian Research Agency, projects P1-0294. E-mail addresses: primoz.potocnik@fmf.uni-lj.si (Primož Potocnik), stephen.wilson@nau.edu (Stephen E. Wilson) ©® This work is licensed under https://creativecommons.org/licenses/by/3.0/ Abstract 2 Ars Math. Contemp. 15 (2018) 39-51 (see Section 1.2 for details). It can also be seen as one of the possible symmetry types of the tetravalent vertex-transitive graphs, namely the one in which the stabiliser of a vertex in some vertex-transitive group of symmetries acts on the neighbourhood as the Klein 4-group in its intransitive action on four points (see [10, Section 1] for more on this topic). This paper is the third in a "trilogy" developing the theory of LR structures. In the first paper [10], we introduced LR structures and we explained their importance in the search for semisymetric graphs via the function P which creates a semisymmetric graph from such a structure. In that paper, we also introduced two related families of LR structures and discussed certain double covers of LR structures. All definitions from [10] appear in the next section; please consult [10] for more details. In the second paper, [9], we showed several purely algebraic constructions for such structures. We first gave a quite general approach to constructing an LR structure from a group having certain automorphisms. We then applied these techniques to several families of abelian groups and to dihedral groups. We noted in [9] that several of these constructions gave semisymmetric graphs having large vertex-stabilizers. It has been known for decades that the size of a vertex-stabilizer in a cubic edge-transitive graph is at most 48 in the dart transitive case (see [12]) and at most 384 in the semisymmetric case (see [4]). No such absolute bounds exist for tetravalent edge-transitive graphs. However, recently Spiga, Verret and the first mentioned author of this paper have discovered efficient bounds on the size of the vertex-stabiliser in terms of the number of the vertices for the case of the tetravalent dart-transitive graphs [7] and for the case of the tetravalent half-arc transitive graphs [11]. Semisymmetric graphs are thus the last remaining case of tetravalent edge-transitive graphs for which no good bounding behavior on the size of the vertex stabilizer is known. Perhaps the examples in [9] and especially the characterisation of the LR structures of type {4, q} in this paper will yield some insight into the phenomenon of the large vertex stabilizer in LR structures, and consequently, the tetravalent semisymmetric graphs of girth 4 (see Section 5). 1.2 Definitions Unless explicitly stated otherwise, all the graphs in this paper are finite, simple and connected. Let A be a regular tetravalent graph and C a partition of its edge-set E(A) into cycles. We shall call such a pair (A, C) a cycle decomposition. Two edges of A will be called opposite at vertex v, if they are both incident with v and belong to the same element of C. The partial line graph of a cycle decomposition (A, C) is the graph P(A, C) whose vertices are edges of A, and two edges of A are adjacent as vertices in P(A, C) whenever they share a vertex in A and are not opposite at that vertex. A symmetry of (A, C) is any permutation of the vertices of A which preserves C. The set of all such is called Aut(A, C). Because the two edges at v that belong to one cycle are connected to both of the edges in the other cycle containing v, the edges at each vertex of A form a 4-cycle in P(A, C). Thus, the girth of P(A, C) is usually 4 and never any larger. A cycle decomposition (A, C) is said to be flexible provided that for every vertex v and each edge e containing v, there is a symmetry which fixes pointwise the cycle D G C containing e and interchanges the other two neighbors of v. The edges joining v to those neighbors are in some other cycle C of C. The symmetry then reverses the cycle C and is called a C-swapper at v. A cycle decomposition (A, C) is called bipartite if C can be partitioned into two subsets P. Potočnik and S. E. Wilson: Linking rings structures and semisymmetric graphs: Comb... 3 G and R so that each vertex of A meets one cycle from G and one from R. Especially in constructions, we will refer to the edges of the cycles in G and those in R as green and red, respectively. The largest subgroup of Aut(A, C) preserving each of the sets G and R will be denoted by Aut+ (A, C), and we will think of it as the color-preserving group of (A, C). Definition 1.1. A cycle decomposition (A, C) is called a linking rings structure (or briefly, an LR structure) provided that it is bipartite, flexible and Aut+(A, C) is transitive on the vertices of A. Note that Aut+(A, C) acts transitively on the darts of each color class, and that (since A is assumed to be connected) its index in Aut(A, C) is at most 2. If there is a symmetry of A which preserves C but interchanges the edge color sets G and R (that is, if Aut+(A, C) = Aut(A, C)), then we say that (A, C) is self-dual. Since the color preserving group Aut+(A, C) of an LR structure (A, C) is transitive on R and on G, all cycles in R must have the same length, say p, and all cycles in G must be of the same length, say q. We then say that the LR structure (A, C) is of type {p, q}. For a self-dual structure, of course, p = q. Two LR structures (Ai, Ci) and (A2, C2) are isomorphic whenever there is a graph isomorphism from A1 to A2 which maps cycles in C1 to cycles in C2. We define the joining sequences of an LR structure to be Jr = [sr, dr, wr ] and Jg = [sg, dg, wg] where: sr is the least s such that some two red cycles are joined by two green paths of length s. The number dr is the least d such that two such green paths have starting points that are d apart on one of the red cycles. If the two paths are j apart on the other red cycle, a symmetry argument shows that d must divide j, and then we set wr = d; see Figure 1. In the case that no two red cycles are joined by two green paths of the same length, we declare Jr to be [0,0,0]. The numbers sg, dg, wg are defined similarly, with colors reversed. If (A, C) is self-dual, Jr structure is not self-dual. bo bi bd 1 Jg. More usefully, if Jr = Jg, then the bj ao aj a d Figure 1: Green paths of length s joining two red cycles. If (A, C) is a cycle decomposition, then a cycle C in A is said to be C-alternating if no two consecutive edges of C belong to the same element of C. If a C-alternating 4-cycle exists, then Jr = Jg = [1,1,1], and (A, C) is the partition of the edges of a toroidal map of type {4,4} into horizontal and vertical cycles. Definition 1.2. An LR structure (A, C) is called suitable provided that (1) (A, C) is not self-dual, and (2) A has no C-alternating 4-cycles. The primary result of [10] is that: 4 Ars Math. Contemp. 15 (2018) 39-51 Theorem 1.3. The partial line graph construction P induces a bijective correspondence between the set of suitable LR structures and the set of worthy tetravalent semisymmetric graphs of girth 4. The word worthy in this statement means that no two vertices of the graph have exactly the same neighbors. Every new suitable LR structure gives a new semisymmetric graph, and so we are interested in finding and creating LR structures. In the remainder of this paper, we show how varied examples can be, concentrating on combinatorial constructions. We first present two simple but non-trivial constructions to show some of the variety possible and to illustrate how the properties of LR structures enter into proofs. 2 Two constructions 2.1 Rows and columns We construct an LR structure RC(n, k) in the following way: the vertices are to be all ordered pairs (i, (r, j)) and ((i, r), j), where i and j are in Zn, and r is in Zk. Green edges join (i, (r, j)) to (i ± 1, (r, j)) and ((i, r), j) to ((i, r), j ± 1), while red edges join (i, (r, j)) to ((i, r ± 1), j) and so ((i, r), j) to (i, (r ± 1, j)). The function (i, (r, j)) ^ (i + 1, (r, j)) and ((i, r), j) ^ ((i +1, r), j) is a symmetry of the graph; we abbreviate it by saying i ^ i + 1. Similarly, each of the functions, j ^ j + 1, r ^ r + 1, i ^ —i, j ^ —j, r ^ —r acts as a symmetry of RC(n, k). These dihedral symmetries act transitively on the vertices of each kind, and the correspondance (i, (r, j)) ^ ((j, r), i) is a symmetry and interchanges the two sets. The green neighbors of (o, (0,0)) are (1, (0,0)) and ( — 1, (0,0)), while the red neighbors are ((0,1), 0) and ((0, —1), 0). Swappers at (0, (0,0)), then, are i ^ — i and r ^ —r. So RC(n, k) with the given coloring is an LR structure. It has 2n2k vertices, and its group has order at least 8n2k. The structure is of type {n, LCM(2, k)}. If k is even, the graph described above is disconnected; in this case, re-assign the name RC(n, k) to the component containing (0, (0,0)). Then the graph has only n2k vertices. It is easy to check that Jr = [1,2,1], while Jg = [2,1,1] and so this structure is always suitable. This LR structure is also described algebraically in [9]. 2.2 SoP In this section, we describe a family of LR structures whose symmetry groups have arbitrarily large vertex stabilizers. The structure is SoP(m, n), where m and n are multiples of 4. Let r = ^ + 1; then we have that r2 = 1 mod n. Further, if j is even, then rj = j, while if j is odd, rj = j + n. The vertex-set is Zm x Zn x Z2. Red edges join (i, j, k) to (i, j ± rk, k); for fixed i and j, green edges join the two vertices (2i, j, 0) and (2i, j, 1) to the two vertices (2i + 1, j, 0) and (2i + 1, j, 1) if j is even, to the two vertices (2i — 1, j, 0) and (2i — 1, j, 1) if j is odd. We claim that each of the following mappings p, a, t, y and S is a symmetry of the structure: (i, j, k)p = (i,j,k)M = (i,j,k)a = (i,j + 2, k) (i, —j, k) (i + 1,j + 1, k) P. Potočnik and S. E. Wilson: Linking rings structures and semisymmetric graphs: Comb... 5 Together, these symmetries show that the structure is vertex-transitive. The symmetry ^ acts as a red swapper at (0,0,0), and S acts as a green swapper there. Thus SoP(m, n) is an LR structure of order 2mn and type {4, n}. The conjugates of S by (a2) commute with each other and so form a subgroup of order 2m. We can see, then, that the order of a In this case, Jr = [1,2,1], while Jg = [2,2,1] and so this structure is always suitable. 3 LR structures from cycle structures 3.1 Voltage graphs and 2-coverings We wish to use the mechanism of voltage graphs to describe a family of LR structures. Let us first summarize the voltage construction and some related facts in the special case of 2-coverings: Let r be any connected graph or multigraph. A Z2-voltage assignment on r is a function Z: E(r) ^ Z2. The corresponding 2-fold covering Cov(r, Z) has V(r) x Z2 as its vertex-set. The edge-set is {{(u, i), (v, i + Z(e))} | e = {u,v} G E(r),i G Z2}. Two Z2-voltage assignments Z and Z' are equivalent provided there is an isomorphism between Cov(r, Z) and Cov(r, Z') which acts trivially on first coordinates. For any vertex v, define the function ^v on the set of all Z2-voltage assignments on r by letting Z^v be the assignment defined by We call such a function a "local reversal". Then Z is equivalent to Z^v, and any two equivalent assignments are related by a series of local reversals. It follows that if Z and Z' are equivalent, then there is a set U C V(r) such that Z(e) = Z '(e) exactly when both ends of e are in U or both not in U. Two voltage assignments Z and Z' are isomorphic provided that some isomorphism 7 of Cov(r, Z) onto Cov(r, Z') has the property that for each vertex v, (v, 0)7 and (v, 1)7 have the same first coordinate. Certainly Z and Z' are isomorphic if there is a symmetry P of r such that Z'(eP) = Z(e) for every e. We write Z' = ZP in this case, and then the function which sends (v, i) to (vP, i) is an isomorphism of Cov(r, Z) onto Cov(r, Z'). Finally, we say that a symmetry a of r lifts to a symmetry a of Cov(r, Z) provided that for each vertex of Cov(r, Z), (v, i)a = (va, j) for some j. Then, clearly, a lifts if and only if Za is equivalent to Z. 3.2 Voltage description of CS(r, B, i) (i, j, = (i,rj, 1 - k) (i,j,k)7 = (-i,j + 1,k) m — 2 vertex-stabilizer is at least 2 2 . (CMv )(e) 1 + Z (e) v is an endvertex of e Z (e) v is not an endvertex of e The construction we wish to present here has to do with a kind of highly symmetric cycle decomposition called a cycle structure: 6 Ars Math. Contemp. 15 (2018) 39-51 Definition 3.1. A cycle structure in a tetravalent graph r is a cycle decomposition B of r such that Aut(r, B) acts transitively on the darts of r. Consider, for example, the graph of the octahedron O, shown in Figure 2. The set B of triangles induced by the triples {{1, 5, 6}, {1, 2, 3}, {2,4, 6}, {3,4, 5}} forms a cycle structure in O. (In what follows, we will refer to each of these triangles by naming the vertex-triple which induces it rather than specifying its edges.) The group Aut(O, B) is isomorphic to the symmetric group S4, is dart-transitive and acts as S4 on the four triangles. In particular, (O, B) is a cycle structure. Cycle structures were introduced in [5], where it was shown that a vast majority of dart-transitive 4-valent graphs admit a cycle structures—many have more than one. At the end of this section we will show all small cycle structures and see how they contribute semisymmetric graphs. 3.3 The multigraph r' and its symmetries We construct an LR structure from a cycle structure (r, B) in two steps: we form a multigraph and then 2-cover it. First form the multigraph r' from r by separating each vertex into a pair of vertices, so that the cycles from B remain cycles but become disjoint. Then connect the two vertices in each pair with two parallel edges. We will refer to these as "bridge" edges. In our example of the octahedron with cycles {1, 5, 6}, {1, 2,3}, {2,4,6}, {3,4,5}; Figure 3 shows the result. To be more specific, the vertices of r' are all (C, v) where C G B, and v G C. "Ordinary" edges join (C, u) to (C, v) where {u, v} is an edge in the cycle C. If v belongs to cycles C and D, the corresponding "bridge" edges ev,0 and eVj1 join (C, v) to (D, v). Continuing the example and setting A = {1,5,6}, B = {1,2, 3}, C = {2,4, 6}, D = {3,4,5}, the corresponding labels of vertices in the split graph are shown in Figure 4. If a is any symmetry in G = Aut(r, B), we choose the canonical representative a' of a to be the permutation which sends the vertex (C, v) to (Ca, va), the ordinary edge {(C, u), (C, v)} to the ordinary edge {(Ca, ua), (Ca, va)}, and the bridge edge eVji to eva,j. Then a' is clearly a symmetry of r'. If we let G' = {a' | a G G}, P. Potočnik and S. E. Wilson: Linking rings structures and semisymmetric graphs: Comb... 7 -(3) Figure 3: The octahedron, split. Figure 4: Labels in the octahedron. then G' = G. Also, for each v e V(r), let av interchange ev,0 and evj1 while fixing every vertex of r' and every edge other than those two. Clearly, each av is in Aut(r'). If we let K = (av : v e V(r)>, then Aut(r') is the inner semidirect product K x G'. For each C e B, define aC to be the product of all av for v e C, and let L = (aC : C e B> < K. Since the product of all aC for C e B involves each av twice, the product is trivial. On the other hand, if D is a proper non-empty subset of C, then an easy connectivity argument shows that the product of all aC for C e D is non-trivial. Therefore the group L has order 2|B|-1. Now, G' is transitive on the vertices of r' and is, in fact transitive on the darts of ordinary edges. So for any (C, v), some a' e G' acts as a swapper of ordinary edges there. And each non-trivial element of L acts as a swapper of bridge edges. Then L x G' is transitive on darts in ordinary edges and on darts in bridge edges as well. Thus the partition C of the edges of r' into cycles covering ordinary edges and cycles covering bridge edges is an LR coloring of this multigraph. 8 Ars Math. Contemp. 15 (2018) 39-51 In the following sections we will construct two covers of the graph r' and show that in both cases, L x G' is the group of symmetries that lifts. 3.4 The coverings of r' We now assign voltages 0,1 from Z2 to the edges of r' in two different ways; the assignments will be called Co and Z1. For bridge edges, let Zi(ev,o) = 0 and Ci(ev,i) = 1 for i = 0,1. We assign Zo(e) = 0 for each ordinary edge e. To define Z1, we choose one edge in each cycle C e B to receive the voltage 1, and assign 0 to the rest of the edges in C. The isomorphism class of the resulting 2-cover is independent of which edge in each cycle is chosen, as we show in the next paragraph. Let A(r, B, 0) and A(r, B, 1) be the 2-covers Cov(r', Zo) and Cov(r', Z1) of r' resulting from Zo and Z1, respectively. Let CS(r, B, 0) and CS(r, B, 1) be these graphs together with the decompositions into cycles covering those in C. In Section 3.5 we will show that CS(r, B, 0) and CS(r, B, 1) are, in fact, LR structures. To support our claim that the isomorphism class of Cov(r', Z1) does not depend on our choice of representatives in each cycle, it will suffice to show that for any C e B, two Z2-assignments which are identical except on two consecutive edges of C are isomorphic assignments. So suppose that vertices u, v, w are consecutive in C, and that one of the assignments is Z such that Z ({(C, u), (C, v)}) = 1, Z ({(C, v), (C, w)}) = 0, as in Figure 6. Then Z is isomorphic to , which in turn is equivalent to M(c,v) (where, ^(c,v) is a local reversal as described in Section 3.1) and this assignment is identical to Z except on the edges {u, v}, {v, w}, as required. Thus, by applying products such as av^(c,v) to the assignment at successive vertices v of C, we can move the edge bearing a 1 from any position in C to any other. By adjusting each cycle in turn, we can show isomorphism of any two such assignments. This in fact shows the following useful fact, which we will refer to later. 0 0 (a) Zo(O') (b) Zi(O') Figure 5: Voltage assignments. Remark 3.2. Let Z be an assignment on r' for which Z(ev,o) = 0 and Z(ev,1) = 1 for every vertex v of r, and let C e B. If the sum of all Z(e) for e e C is 0, then Z is isomorphic to P. Potočnik and S. E. Wilson: Linking rings structures and semisymmetric graphs: Comb... 9 Figure 6: Isomorphic voltage assignments. some assignment Z' with Z'(e) = 0 for all e G C. Similarly, if the above sum is 1, then Z is isomorphic to some assignment in which every edge of C except one has weight 0, and that one has weight 1. Consequently, every 2-cover of r' without multiple edges in which all cycles covering those in B have the same length must be isomorphic to CS(r, B, 0) or cs(r, b, 1). ♦ 3.5 The groups of CS(r, B, 0) and CS(r, B, 1) We will show in this section that the cycle decompositions CS(r, B, 0) and CS(r, B, 1), are LR structures, each admitting a group of order 2|B| |G|. Let G = Aut(r, B). Since (r, B) is a cycle structure, G is transitive on the darts of r. Further, let G', K and L be the groups of symmetries of r' as defined in Section 3.3, and recall that Aut(r') = K x G'. Observe that, since G' maps a cycle in B to another cycle in B and since L is generated by all oc, C G B, L is normalised by G' and hence normal in Aut(r'). In particular, (L, G') = L x G'. Fix i G {0,1} and let T be the group of those symmetries of r' that lift to a symmetry of CS(r, B, i). In view of Section 3.1, a symmetry P of r' is in T if and only if the voltage assignment ZiP is equivalent to Zi. We will prove that T = L x G' and that the lift of T contains the symmetries needed to show that CS(r, B, i) is an LR structure. Let us first show that for every a G G (and thus a' G G') there exists P G T such that P G a'K. In other words, we show that G' C TK, and since G'K = Aut(r'), that Aut(r') = G'K = TK. If i = 0, then Zia' = Zi, implying that a' lifts, and we can take P to be a' itself. Suppose now that i — 1. Then Zia' also has one edge in each C G B whose voltage is 1. Then as in Section 3.4, there is a (possibly empty) subpath v1, v2, v3,..., vr of C such that Z1a'aviM(c,Vi)... oVkM(c,Vr) coincides with Z1 on C. Denote O(a,C) = Ovi OV2 ••• °vr and M(a,C) = V(C,vi)V(C,V2) M(C,vr) and observe that ^'s and the o's commute in their action on voltage assignments. Hence, by performing this adjustment for each C G B in turn, it follows that k k Z1 = Z1a'n O(a,Cj ) n P(",Cj) j=1 j=1 10 Ars Math. Contemp. 15 (2018) 39-51 and so, letting k =n a(a'°i) g j=i we see that Ci^ is equivalent to Qi and thus that fi G T. This completes the proof of the claim that Aut(r') = G'K = TK. Let us now show that TnK = L. This will then imply that G' = G'K/K = TK/K = T/(T n K) = T/L and hence that T = L x G', as claimed. First note that each element of L lifts, and hence L < T .To see this, let a G L and thus a = f] ceI) ac for some DC B. Since (Zi 2 . We describe a k-covering of r', and we call the covering structure CS(T, B, k). Give the weight 0 to each ordinary edge. Give each pair of bridge edges voltage 1 in opposite directions. Let CSI(r, B, k)) be one component of the resulting k-cover. If (r, B) is bipartite and k is even, then the k-covering has two components, while in all other cases, it has one. Thus if B has m cycles, each of length n, and so mn/2 vertices, then CSI(r, B, k)) is of type {n, LCM(2, k)} and has mnk or mnk/2 vertices. It is easy to check that Jr = [2,1,1], while Jg = [1, 2,1] and so this structure is always suitable. 4 Other constructions 4.1 Locally circular cycle structures Definition 4.1. Suppose C is a cycle decomposition of a graph r of valence 2q and let X be the set of all (C, v) such that C G C, v g V(r) and C passes through v. For a vertex v of r let Xv be the set of pairs with second coordinate v. If P is a permutation on X such that the orbits of (P} are the sets Xv for v g V(r), then we will say that (r, C, P) is locally circular. We will call such a P a locally circular ordering on (r, C). Definition 4.2. If a is a symmetry of (r, C), we will say that a respects P provided that, for each (C, v) G X, (C, v)Pa is either (Ca, va)P or (Ca, va)P-1. Let Aut(r, C, P) be the group of all symmetries of (r, C) which respect P. Definition 4.3. If (r, C, P) is locally circular and G < Aut(r), we will say it is G-locally dihedral provided that the following hold: (i) G acts transitively on darts, (ii) every element of G respects P, (iii) for every v G V(r), the stabiliser Gv acts dihedrally on the cycles through v and contains an element which fixes every cycle through v setwise and reverses at least one of them. A locally circular (r, C, P) is locally dihedral if it is G-locally dihedral for some G < Aut(r). While this definition appears to be very restrictive, notice that a large class of examples arises from reflexible maps: if M is a reflexible map of type {p, 2q}, we can consider two edges to be opposite at v provided that those edges are q apart in the cycle of edges incident to v. If M is proper (i.e., no two edges have the same endpoints), the edges fall into cycles in which each edge is joined to the edges opposite it at each end. Then the family of such cycles is a locally dihedral cycle structure. Construction 4.4. If (r, C, P) is locally circular, let LDCS(r, C, P) be the bipartite cycle decomposition (A, D) in which vertices of A are all (C, v) such that v is a vertex of cycle C G C, green edges are all {(C, u), (C, v)} such that {u, v} is an edge of cycle C G C, and red edges are all {(C, v), (C, v)P}. 15 Ars Math. Contemp. 15 (2018) 39-51 Theorem 4.5. If (T, C, P) is a locally dihedral cycle structure, then LDCS(T, C, P) is an LR structure which has no alternating 4-cycles. Proof. Every element of G = Aut(T, C, P) acts on LDCS(T, C, P) as a symmetry. Since G is transitive on darts, Aut(LDCS(T,C, P)) is transitive on vertices. To see that it is flexible, consider a vertex (C, v). Because (r, C, P) is locally dihedral, it has a symmetry p G G which fixes v, fixes each cycle at v setwise and reverses C. Then p acts as a green swapper at (C, v). Also, because Gv acts dihedrally on the cycles at v, it has a ^ which fixes C (setwise) and interchanges the neighboring cycles in the local order. Then ^ or ^p is a red swapper at (C, v). If there were an alternating 4-cycle in LDCS(r, C, P), the green edges would correspond to distinct edges in r with the same endpoints, which is forbidden in a graph. □ Our last results in this paper show that the constructions CS and LDCS generate all LR structures (A, C) for which C contains cycles of length 3 or 4. We begin by showing that LDCS covers all the cases in which sr > 2. Theorem 4.6. Let (A, C) be an LR structure of type {p, q} in which no two red cycles (of length p) are joined by more than one green edge (that is, if the joining sequence Jr is not of the form [1, *, *]). Then there is a locally dihedral cycle structure (r, D, P), where r is a graph of valence 2p and D is a partition of the edges of r into q-cycles, such that (A, C ) and LDCS(r, D) are isomorphic LR structures. Proof. Let r be the graph with the vertex set being the set of red cycles in (A, C) with two red cycles adjacent in r whenever they are joined by a green edge in A. For each vertex v of A, let n(v) be the red cycle to which v belongs. We can consider n to be a projection onto r of the subgraph of A induced by its green edges. Since two red cycles are joined by at most one green edge, this projection n induces a bijection between the green edges in (A, C) and the edges of r. Let D be the set of all cycles in r of the form n(D) where D is a green cycle in (A, C). Then r has valence 2p and D is a cycle decomposition of r in which every cycle has length q. Let X be the set of all (n(D), C) such that D is a green cycle in (A, C) and C is a red cycle in (A, C) contained (as a vertex of r) in the cycle n(D). Let us now define the permutation P on X yielding a locally dihedral (r, D, P). For each red cycle C in (A, C) choose one of the two possible orientations of C. We then let P map a pair (n(D), C) G X to the pair (n(D'), C) where D' is the green cycle through the next vertex (with respect to the chosen orientation of C) on C after the unique vertex of A that belongs to both C and D. Then all of Aut+ (A, C) respects this P. Since Aut+(A, C) is transitive on green darts, it acts dart-transitively on r. The set stabilizer of a red cycle acts dihedrally on the set of green cycles meeting it. Any green swapper fixes a red cycle pointwise and so fixes setwise each green cycle meeting it, and reverses at least one cycle. Thus (r, D, P) is a locally dihedral cycle structure. Finally, let ^ be the mapping which maps a vertex v of A to the vertex (n(D), C) of LDCS(r, D, P) where C and D are the red and the green cycle of (A, C) containing v, respectively. It is a matter of straightforward computation to verify that ^ is an isomorphism of the LR structures (A, C) and LDCS(r, D). □ With Theorem 4.6, we can now easily prove that all LR structures of types {3, q} or {4, q} without alternating 4-cycle arise by constructions in this paper. (We point out that P. Potočnik and S. E. Wilson: Linking rings structures and semisymmetric graphs: Comb... 29 the LR structures with alternating cycles have been characterised in [10, Lemma 6.3].) The first of the two corollaries below follows directly from Theorem 4.6 after observing that an alternating 4-cycle implies that two red cycles are joined by two green edges. The second one requires some additional work. Corollary 4.7. If (A, C) is a LR structure of type {3, q} without alternating 4-cycles, then there is a locally dihedral cycle structure (r, D, P), where r is a graph of valence 6 and D is a partition of the edges of r into q-cycles, such that (A, C) and LDCS(r, D) are isomorphic LR structures. Theorem 4.8. If (A, C) is an LR structure of type {4, q} without alternating 4-cycles, then one of the following happens: (1) there is a locally dihedral cycle structure (r, D, P), where r is a graph of valence 8 and D is a partition of the edges of r into q-cycles, such that (A, C) = LDCS(r, D); or (2) there is a cycle structure (r, B), where r has valence 4 and (A, C) = CS(r, B, i) for i = 0 or 1. Proof. Suppose that (A, C) is an LR structure, without alternating 4-cycles, in which the red cycles have length 4. Consider a green edge and the red cycles through its endvertices. If no other green edge joins those red cycles then Theorem 4.6 applies, and so (1) holds. If not, then, because (A, C) has no alternating 4-cycles, two green edges join two antipodal vertices on one red cycle with two antipodal vertices on the other red cycle. Call two green edges which are arranged in this way, mated edges. Then Jr = [1, 2,1]. Collapsing each red cycle to a single vertex, as in the proof of Theorem 4.6, identifies all pairs of mated green edge to form a tetravalent dart-transitive graph r. The green cycles of (A, C) are projected onto a cycle structure D in r. Since the projection is 2-to-1 on green edges, we see that if mated green edges come from different cycles, those two q-cycles project to a single q-cycle in r. If they are from the same cycle, then q must be even and that cycle projects onto a §-cycle. Consider now an intermediate projection in which we identify mated green edges, and within a red cycle identify antipodal vertices and opposite edges. This projects (A, C) onto a multigraph, in which the red "cycles" are actually 2-gons, i.e., each consists of a pair of parallel red edges. This is clearly isomorphic to the graph r' formed in the first step of the construction of CS(r, D, i). This presents (A, C) as a 2-covering of r'. Remark 3.2 shows that in the case where the green cycles of r are of length q, the LR structure (A, C) is isomorphic to CS(r, D, 0), and if the green cycles are of length §, then (A, C) is isomorphic to CS(r, D, 1). □ 5 Conclusion Though this paper and its predecessors [9, 10] have presented a number of constructions both agebraic and combinatorial, much remains to be done. Every new discovery of an LR structure gives us a new semisymmetric graph of girth and valence 4. Thus, finding LR structures and organizing them into parameterized families is important in the search for semisymmetric graphs. The smallest known LR structure not yet to be seen as part of a family of such has 36 vertices, and there are seven more with 72 vertices. Examples such 17 Ars Math. Contemp. 15 (2018) 39-51 as SoP, CS(r, B, 0) and CS(T, B, 1), whose vertex-stabilizers can grow without bound add to our growing knowledge about the structure of semisymmetric graphs. Our ultimate goal of the study of the LR structures is to develop the tools that would enable us to construct a complete list of all "small" LR structures. Such lists exist for both types of edge-transitive cubic graphs (see [1, 3] for the census of cubic edge-transitive graph of order at most 768 and [2] for the extension to order up to 10 000 in the case of dart-transitive graphs) and for cubic vertex-transitive graphs [6] for orders up to 1280. Moreover, lists of all dart-transitive and 1 -transitive tetravalent graphs of order up to 1000 have recently been compiled (see [6, 8]). The main ingredient of these results was always a theoretical result that bounded the order of the vertex-stabiliser in such a graph. While it has long been known that this order is bounded by a constant in the case of cubic edge-transitive graphs, this is not the case in the cubic vertex-transitive or tetravalent edge-transitive cases. What is more, for these cases, families of graphs where the order of the stabiliser grows exponentially with the order of the graph are known. The crucial point in the enumeration of these graphs was a result that identified the "problematic" families and proved that the order of the vertex-stabiliser in the "non-problematic" graphs is bounded by a tame (possibly sublinear) function of the order of the graph. As it happens, all the problematic graphs contain cycles of girth 4 (and there is a deep group theoretical reason for that). There is strong evidence that a similar result might hold in the case of the LR structures. This leads to the following question (we thank Gabriel Verret for a fruitful discussion on this topic): Question 5.1. Does there exist a polynomial function f such that for every LR structure (A, C) of type other than {4, q}, the symmetry group Aut(A, C) has order at most f (|V (A)|). This question complements Corollary 4.8 which reduces the classification of the LR structures of type {4, q} to the study of 8-valent locally dihedral cycle structures and cycle structures in tetravalent dart-transitive graphs. References [1] M. D. E. Conder and P. Dobcsanyi, Trivalent symmetric graphs on up to 768 vertices, J. Com-bin. Math. Combin. Comput. 40 (2002), 41-63. [2] M. D. E. Conder, C.-H. Li and P. Potocnik, On the orders of arc-transitive graphs, J. Algebra 421 (2015), 167-186, doi:10.1016/j.jalgebra.2014.08.025. [3] M. D. E. Conder, A. Malnic, D. Marusic and P. Potocnik, A census of semisymmetric cubic graphs on up to 768 vertices, J. Algebraic Combin. 23 (2006), 255-294, doi:10.1007/ s10801-006-7397-3. [4] D. M. Goldschmidt, Automorphisms of trivalent graphs, Ann. Math. 111 (1980), 377-406, doi:10.2307/1971203. [5] S. Miklavic, P. Potocnik and S. Wilson, Arc-transitive cycle decompositions of tetravalent graphs, J. Comb. Theory Ser. B 98 (2008), 1181-1192, doi:10.1016/j.jctb.2008.01.005. [6] 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. [7] P. Potocnik, P. Spiga and G. Verret, Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs, J. Comb. Theory Ser. B 111 (2015), 148180, doi:10.1016/j.jctb.2014.10.002. P. Potočnik and S. E. Wilson: Linking rings structures and semisymmetric graphs: Comb... 31 [8] P. Potočnik, P. Spiga and G. Verret, A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two, Ars Math. Contemp. 8 (2015), 133-148, doi:10.26493/ 1855-3974.559.c6c. [9] P. Potocnik and S. Wilson, Linking rings structures and semisymmetric graphs: Cayley constructions, Eur. J. Combin. 51 (2016), 84-98, doi:10.1016/j.ejc.2015.05.004. [10] P. Potocnik and S. E. Wilson, Linking rings structures and tetravalent semisymmetric graphs, Ars Math. Contemp. 7 (2014), 341-352, doi:10.26493/1855-3974.311.4a8. [11] P. Spiga and G. Verret, On the order of vertex-stabilisers in vertex-transitive graphs with local group Cp x Cp or Cp wr C2, J. Algebra 448 (2016), 174-209, doi:10.1016/j.jalgebra.2015.09. 033. [12] W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947), 459-474, doi:10.1017/s0305004100023720. [13] S.Wilson, Rose window graphs, Ars Math. Contemp. 1 (2008), 7-19, doi:10.26493/1855-3974. 13.5bb.