/^creative ^commor
ARS MATHEMATICA
CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ars mathematica contemporanea 8 (2015) 177-194
Regular embeddings of cycles with multiple edges revisited
Dedicated to Dragan Marusic on the occasion of his 60th birthday
Kan Hu
Faculty of Natural Sciences, Matej Bel University,
974	01 Banska Bystrica, Slovakia
and
Institute of Mathematics, Slovak Academy of Sciences,
975	49 Banska Bystrica, Slovakia
and
School of Mathematics, Physics and Information Science, Zhejiang Ocean University, Zhoushan, Zhejiang 316000, People's Republic of China
Roman Nedela
Faculty of Natural Sciences, Matej Bel University,
974	01 Banskà Bystrica, Slovakia
and
Institute ofMathematics, Slovak Academy ofSciences,
975	49 Banska Bystrica, Slovakia
Martin Skoviera
Department of Computer Science, Comenius University, 842 15 Bratislava, Slovakia
Naer Wang
Faculty of Natural Sciences, Matej Bel University, 974 01 Banska Bystrica, Slovakia and
School ofMathematics, Physics and Information Science, Zhejiang Ocean University, Zhoushan, Zhejiang 316000, People's Republic of China
Received 10 March 2014, accepted 13 May 2014, published online 28 September 2014
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
178
Ars Math. Contemp. 8 (2015) 133-148
Abstract
Regular embeddings of cycles with multiple edges have been reappearing in the literature for quite some time, both in and outside topological graph theory. The present paper aims to draw a complete picture of these maps by providing a detailed description, classification, and enumeration of regular embeddings of cycles with multiple edges on both orientable and non-orientable surfaces. Most of the results have been known in one form or another, but here they are presented from a unique viewpoint based on finite group theory. Our approach brings additional information about both the maps and their automorphism groups, and also gives extra insight into their relationships.
Keywords: Regular embedding, multiple edge, Holder's Theorem, Möbius map. Math. Subj. Class.: 20B25, 05C10
1 Introduction
Classification of all regular embeddings of a given graph on orientable or non-orientable surfaces has been addressed by many researchers in topological graph theory. On the abstract level, the classification problem was solved by Gardiner et al. where graphs which underlie a regular map were characterised by means of a condition requiring the existence of certain subgroups in the graph automorphism group [7]. This condition allows one to identify all existing map automorphism groups within the graph automorphism group and subsequently to determine all regular embeddings of the graph that have a specified subgroup as its automorphism group. Nevertheless, practical application of the condition depends on understanding the structure of the automorphism group of the graph and therefore has serious limitations. At present, a complete classification is known for only a few infinite classes of graphs, most notably, for complete graphs [8, 9, 27], complete bipartite graphs [11, 22], hypercubes [4, 14, 21], and for several others basic classes of graphs (see for example [6, 29]).
In this paper we focus on regular maps whose underlying graph is a cycle with multiple edges; for brevity we call such maps multicyclic. Multicyclic maps can be regarded as combinations of two well understood families of maps: spherical embeddings of cycles and dipole maps. The study of these maps has a fairly long history which exceeds the context of the proper topological graph theory [1, 3, 5, 17]. In early papers, these maps typically occur in the dual form as maps where each face meets precisely two others; in [26] such maps are called bicontactual. An important special case, regular maps with two faces, was extensively discussed by Coxeter and Moser in their celebrated book [5], mentioning much older works of Brahana [2] and Threlfall [24]. In full generality, bicontactual regular maps were first considered in 1985 by Wilson [26]. Using a geometric approach depending on tracing map diagrams Wilson derived a classification of bicontactual maps on both orientable and non-orientable surfaces. Unfortunately, his result does not immediately translate via surface duality to regular embeddings of cycles with multiple edges, and even the basic information such as the orientability character or the number of regular
E-mail addresses: kanhu@savbb.sk (Kan Hu), nedela@savbb.sk (Roman Nedela), skoviera@dcs.fmph.uniba.sk (Martin Skoviera), naerwang@savbb.sk (Naer Wang)
K. Hu et al.: Regular embeddings of cycles with multiple edges revisited
179
embeddings for a given length and multiplicity of a cycle is hard to extract.
In 1989, Wilson [27, Theorem 3] proved that a regular embedding of any graph with multiple edges is either a totally branched covering over a regular embedding of the corresponding simple graph, or a cantankerous map, a regular map with edge-multiplicity 2 where every 2-cycle is orientation-reversing. He went on to show that (among other things) an even cycle has a regular embedding with every multiplicity while an odd cycle has a regular embedding with every odd multiplicity but with no even multiplicity.
Cantankerous maps, under a more appropriate term Mobius regular maps, were again studied by Li and Siran in [15, 16] within the context of maps with an unfaithful action of the automorphism group on the vertex set. With the help of general results about unfaithful maps they produced a classification of all multicyclic regular maps on both orientable and non-orientable surfaces [15, Propositions 7 and 8]. In particular, they proved that the doubled n-cycle admits a Mobius regular embedding if and only if n is divisible by 3. Nevertheless, neither the enumeration of isomorphism classes of the maps nor orientable regularity were treated in their papers.
To complete the history of classification of multicyclic regular maps we should mention an unpublished work of Skoviera and Zlatos [23] where a general framework for the study of regular embeddings of graphs with multiplicity m based on Zm-valuations was developed. In a subsequent work [22], this theory was applied to deriving a classification of orientably regular embeddings of multicycles. Although the latter classification enables enumeration, no information about the automorphism groups of the maps was given.
The present paper intends to complete the picture of multicyclic regular maps by providing a detailed description, classification, and enumeration of multicyclic maps on both orientable and non-orientable surfaces along with additional information about the automorphism groups of maps and relationships between them. In contrast to the majority of previous papers on this topic we deal with both orientably regular maps (where map automorphisms are necessarily orientation-preserving) and with regular maps (where map automorphisms include reflections and the maps may also lie on non-orientable surfaces). Our interest in these maps is substantiated by the fact that large classes of regular maps have multicyclic quotients and that multicyclic maps can often serve as important extremal examples [1, 3, 17].
The following two theorems, stated in a simplified enumerative form, are our main results. More detailed statements can be found in the subsequent sections. Throughout the paper C*im) denotes the graph resulting from the cycle Cn of length n by replacing each edge with m parallel edges.
Theorem 1.1. Let p be the number of orientably regular embeddings of the graph Cim) where n > 3 and m > 2, and let p(m) denote the number of solutions of the congruence e2 = 1 (mod m). Then
(i)	p = 0 if n is odd and m is even,
(ii)	p =1 if both n and m are odd,
(iii)	p = p(m) if n is even and m is odd,
(iv)	p = 2p(m) if n = 0 (mod 4) and m is even,
(v)	p = 2p(2m) if n = 2 (mod 4) and m is even.
Furthermore, all these embeddings are reflexible.
180
Ars Math. Contemp. 8 (2015) 133-148
Theorem 1.2. Let q be the number of non-orientable regular embeddings of the graph where n > 3 and m > 2. Then
(i)	q =1 if both n and m are odd, in which case the antipodal double cover of the map is an orientably regular embedding of C^ corresponding to the solution e = —1 of the congruence e2 = 1 (mod m) listed in item (iii) of Theorem 1.1,
(ii)	q =1 if n = 0 (mod 3) and m = 2, in which case the map is a Mobius map, and
(iii)	q = 0 in all other cases.
Theorem 1.2 has an interesting corollary which strengthens a result of Wilson [26] and shows that there exist no regular maps with nilpotent automorphism group on non-orientable surfaces of genus greater than 1. In contrast, nilpotent regular maps on orientable surfaces of arbitrarily large genus are abundant; for further information see [18].
Theorem 1.3. There exist no non-orientable regular maps whose automorphism group is nilpotent except the dihedral embeddings of bouquets of 2n circles into the projective plane and their duals, embeddings of cycles of length 2n, for n > 1.
2 Orientably regular embeddings of
It is well-known that every d-valent orientably regular map M can be identified with a triple (G; x, y) where G is a finite group and {x, y} is a generating set for G with xd = y2 = 1; see, for example [10, 21]. Such a triple is called an algebraic orientably regular map. Elements of the group represent darts of M, that is, edges endowed with an orientation. The right translation g ^ gx, g G G, by the generator x corresponds to the rotation of the map, the permutation that cyclically permutes darts directed away from vertices consistently with the orientation of the surface. The translation g ^ gy, g G G, by the generator y corresponds to the dart-reversing involution, which switches the direction of each dart to the opposite direction. The vertices, edges, and faces of M are in a one-to-one correspondence with the left cosets of (x), (y), and (xy), respectively, and the incidence between the objects corresponds to non-empty intersection of cosets.
A map homomorphism (G; x, y) ^ (G'; x', y') between algebraic maps (G; x, y) and (G'; x', y') is a group homomorphism G ^ G' that takes x to x' and y to y'. In topological terms, a map homomorphism corresponds to an orientation-preserving covering projection of maps, possibly branched over vertices, face-centres, and free ends of semiedges (where the branching index must be 2). It follows that two algebraic maps (G; x, y) and (G; x', y') represent isomorphic orientably regular maps if and only if there is an automorphism of G taking x to x' and y to y'. Each automorphism of the map M = (G; x, y) corresponds to a left translation g ^ ag, g G G, where a is a fixed element of G. In particular, the group Aut+(M) of all orientation preserving automorphisms of M is isomorphic to G. The map automorphism corresponding to the generator x generates a cyclic vertex-stabiliser in the automorphism group of (G; x,y), while y generates the edge-stabiliser, which is necessarily of order two. An orientably regular map M = (G; x, y) is reflexible if it is isomorphic to its mirror image M-1 = (G; x-1, y); otherwise (G; x, y) is chiral.
In what follows, we often identify the group G that underlies an algebraic map M = (G; x, y) with its left regular representation, and it should be easy for the reader to see from the context which notion is in use.
K. Hu et al.: Regular embeddings of cycles with multiple edges revisited
181
Before proceeding to the classification of orientably regular embeddings of cycles with multiple edges we present a general result about orientably regular embeddings of graphs with multiple edges. For a non-trivial simple graph X let X(m) denote the graph arising from X by replacing each edge with m parallel edges. To avoid trivial cases, the multiplicity m of every graph X(m) will always be at least 2. We show that every orientably regular embedding of X(m) determines two orientably regular maps, an orientably regular embedding of X and a regular embedding of the dipole graph Dm with multiplicity m, which consists of two vertices and m parallel edges joining them. In this context it may be useful to recall a result from [19] and [18] that every orientably regular embedding of Dm is isomorphic to a map D(m, e) arising from the metacyclic group G(m, e) given by the presentation
G(m, e) = (x, y | xm = y2 = 1, yxy = xe).
where e2 = 1 (mod m). Moreover, two dipole maps D(m, e) and D(m, e') are isomorphic if and only if e = e' (mod m).
We are now ready for the result about the structure of orientably regular maps with multiple edges.
Theorem 2.1. Let M = (G; x, y) be a regular map of valency d with underlying graph X(m) of order at least 2. Set A = (xd/m) and B = (xd/m, y). Then:
(i)	The group A is a normal subgroup of G, the map M/A = (G/A; xA,yA) is a regular embedding of X, and the natural projection M ^ M/A is a map homo-morphism bijective on the vertices.
(ii)	M' = (B; xd/m, y) is a dipole map isomorphic to D(m, e) for some integer e such that e2 = 1 (mod m).
(iii)	G = (x,y | xkm = y2 = 1,yxk y = xek,...), where e2 = 1 (mod m) and k = d/m is the valency of X. In particular, the multiplicity m of M is the largest positive divisor q of d such that (xd/q) < G.
(iv)	If M is not bipartite, then e = 1 (mod m).
Proof. By our assumption, M contains neither loops nor semiedges. Since any two vertices of M are joined by m parallel edges and G acts regularly on the darts of M, the subgroup A = (xk) fixes two vertices and acts regularly on the set of edges joining them. Applying the regularity again, A fixes all the vertices of M pointwise. In particular, A is a normal subgroup of G. The natural projection M = (G; x, y) ^ (G/A; xA, yA) = M/A is a map homomorphism which is bijective on the vertices. It follows that the underlying graph of M/A is X. This proves (i).
By definition, y transposes a pair of adjacent vertices. It follows that M' = (B; xk, y) is an orientably regular map with two vertices and m parallel edges. Since B contains the cyclic group A as a subgroup of index 2, B is a metacyclic group with presentation
B = (xk, y | (xk)m = y2 = 1, (xk)y = xek)
where e2 = 1 (mod m) (see [19]). It follows that G has a presentation as stated in (iii). In particular, we see that the multiplicity m of M is the largest positive divisor q of d such that (xd/q) < G. This proves (ii) and (iii).
To finish the proof, assume that M is non-bipartite. Thus there exists a relation
w(x, y) = xai yx°2y .. . x°2r+1 y = 1
182
Ars Math. Contemp. 8 (2015) 133-148
where y appears an odd number of times, say 2r + 1 times. Then
xd/m = xd/mw(x,y) = w(x,y)(xd/m)e2r+1 = xde/m,
and hence e = 1 (mod m), as required.	□
Now we proceed to multicyclic regular maps. We start by introducing a family of orientably regular maps C(n, m; e, f) as follows. Let C(n, m; e, f) = (G; x, y) where G = G(n, m; e, f) is a group given by the presentation
G(n, m; e, f) = (x, y | x2m = y2 = 1, y-1x2y = (x2)e, (xy)n = (x2)f >. (2.1)
The parameters m and n are positive integers, n > 3, and e, f G Zm.
We now show that every orientably regular embedding of Cim) is isomorphic to one of the maps C(n, m; e, f) for suitable integers e and f, and classify these maps up to isomorphism.
Theorem 2.2. The graph C^, with n > 3 and m > 2, has an orientably regular embedding for each n and m, unless n is odd and m is even. Every such embedding is reflexible and is isomorphic to one of the maps C(n, m; e, f) where e and f are as follows:
(i)	If both n and m are odd, then e =1 and f = (n + m)/2 (mod m). In particular, there is only one orientably regular embedding in this case.
(ii)	If n = 0 (mod 4) and m is odd, then e2 = 1 (mod m) and f = (e + 1)n/4 (mod m).
(iii)	If n = 2 (mod 4) and m is odd, then e2 = 1 (mod m) and f = ((e +1)n + 2m)/4 (mod m) for even e, and e2 = 1 (mod 2m) and f = (e +1)n/4 (mod m) for odd e.
(iv)	If n = 0 (mod 4) and m is even, then e2 = 1 (mod m) and f = (e + 1)n/4 (mod m) or f = ((e + 1)n + 2m)/4 (mod m).
(v)	If n = 2 (mod 4) and m is even, then e2 = 1 (mod 2m) and f = (e + 1)n/4 (mod m) or f = ((e + 1)n + 2m)/4 (mod m).
Two such embeddings C(n, m; e, f) and C(n, m; e', f') are isomorphic if and only if e = e' (mod m) and f = f' (mod m).
Reflexible orientably regular embeddings of cim) were previously classified in [15, Proposition 7] leaving the possibility for the existence chiral maps open. It follows from Theorem 2.2 that no chiral embeddings of C(m) exist and therefore the two families coincide.
Our proof of Theorem 2.2 uses a classical result of Holder concerning the structure of metacyclic groups (see Zassenhaus [28, p. 99]).
Theorem 2.3 (Holder's Theorem). Every extension of a cyclic group of order m > 2 by a cyclic group of order n > 2 is determined by two integers e and f satisfying the congruences
en = 1 (mod m) and f (e — 1) = 0 (mod m),
K. Hu et al.: Regular embeddings of cycles with multiple edges revisited
183
and is isomorphic to the group G(e, f) with presentation
G(e,f) = (a,b | am = 1,bn = af ,b—1ab = ae).
Furthermore, the extension determined by e and f is equivalent to that determined by e' and f' if and only if e = e' (mod m) and f = f' (mod m).
Proof of Theorem 2.2. Let M = (G; x, y) be an orientably regular embedding of the graph Cim). By Theorem 2.1(i), A = (x2) < G and M/A = (G/A; xA,yA) is an orientably regular embedding of the simple cycle Cn, where
G/A = (x, y | x2 = y2 = (xy)n = 1).
By Theorem 2.1(iii), the group G has the presentation (2.1) for some e,f G Zm where
e2 = 1 (mod m).	(2.2)
Set a = x2 and b = xy. Then K = (a, b) is a metacyclic group with presentation
(a,b | am = 1,bn = af,ab = ae).	(2.3)
We apply Holder's Theorem to conclude that e and f satisfy the congruences
f (e - 1) = 0 (mod m)	(2.4)
and
en = 1 (mod m).	(2.5) From the presentation of G we deduce that
ay = ae and by = (xy)y = yx = yx2x-1 = x2eyx-1 = aeb-1. For brevity, denote s = J2 n—o1 e% ■ Then
af (2=4) aef = (af )y = (bn)y = (by)n = (aeb—1)n = asb—n = as—f,
whence
2f = s (mod m).	(2.6)
In the above proof we see that G = K x (y), and hence G has an alternative presentation
G = (x,y la = x2,b = xy,am = 1,bn = af ,ab = ae,y2 = 1,ay = ae,by = aeb—1).
(2.7)
Conversely, given a group G defined by (2.1) (or equivalently by (2.7)) with the parameters n, m, e, and f satisfying (2.2), (2.4), (2.5) and (2.6), we see that |G| = IK x (y)l = 2IK|, and from Holder's Theorem we get that |G| = 2mn. By Theorem 2.1, the map (G; x, y) corresponds to an orientably regular embedding of C^.
Recall that two embeddings C(n, m; e, f) = (G(n, m; e, f); x, y) andC(n, m; e', f') = (G(n,m; e',f'); x',y') are isomorphic if and only if the assignment x ^ x', y ^ y'
184
Ars Math. Contemp. 8 (2015) 133-148
extends to a group isomorphism. Routine calculations show that this occurs if and only
if e = e' (mod m) and f = f' (mod m). For the maps (G(n, m; e, f); x,y) and (G(n, m; e, f); x-1, y) the latter condition is clearly satisfied, which immediately implies that each of the maps C(n, m; e, f) is reflexible.
To obtain more details on these embeddings we need to solve the system of congruences (2.2), (2.4), (2.5) and (2.6). First notice that if n is odd and m is even, then e is odd. According to (2.2) we have e2 = 1 (mod m), and therefore s = X™—)1 el = (n - 1)(e + 1)/2 +1. However, 4|(n - 1)(e +1), so s is odd, violating (2.6). In other words, if n is odd and m is even, Cim) does not admit any orientably regular embedding. Our discussion now splits into five cases dealing with the remaining conditions on n and m, each corresponding to an item of Theorem 2.2.
Case (i). Both n and m are odd.
Theorem 2.1 (iv) yields that e = 1 (mod m). By substituting e =1 into (2.6) we get 2f = n (mod m), which implies that 2f = (n + m) (mod m) and consequently 2(f — (n + m)/2) = 0 (mod m). Since m is odd, we infer that f = (n + m)/2 (mod m), and Case (i) is done.
Now we deal with the cases where n is even. Using (2.2) we get s = J2n—o e® = (e + 1)n/2. Substituting for s into (2.6) we obtain
Case (ii). n = 0 (mod 4) and m is odd.
Since n = 0 (mod 4), from (2.8) we get f = (e + 1)n/4 (mod m). By substituting f into (2.4) we obtain
Therefore e and f satisfy (2.4), and Case (ii) is done.
Case (iii). n = 2 (mod 4) and m is odd.
If e + 1 is even, then f = (e + 1)n/4 (mod m). By substituting f into (2.4) we obtain n(e2 — 1)/4 = 0 (mod m). Since n = 2 (mod 4), we get e2 — 1 = 0 (mod 2). If we combine this with (2.2), we get e2 = 1 (mod 2m).
If e+1 is odd, then (e+ 1)n/2 is odd, and hence (e+ 1)n/2+m is even. We may rewrite (2.8) in the form 2f = (e + 1)n/2 + m (mod m), and obtain f = ((e + 1)n + 2m)/4 (mod m). By substituting f into (2.4) we further get
2f = (e + 1)n/2 (mod m).
(2.8)
f (e - 1) = (e2 - 1)n/4 = 0 (mod m).
,2
(2.9)
n(e2 - 1)/2 + m(e - 1) = 0 (mod 2m).
Since m is odd, by the Chinese Remainder Theorem, this is equivalent to
(mod 2).
(2.10a) (2.10b)
By applying (2.2) we may conclude that (2.10a) holds. Since n/2, m, e +1, and e - 1 are all odd, we see that (2.10b) holds, too. Hence (2.4) is satisfied by e and f exactly when the conditions in the statement are satisfied. This completes Case (iii).
K. Hu et al.: Regular embeddings of cycles with multiple edges revisited
185
Case (iv). n = 0 (mod 4) and m is even.
In this case (2.8) has two solutions f = (e + 1)n/4 and f = (e + 1)n/4 + m/2 in Zm. If we insert them into (2.4), we see that (2.4) is satisfied, and Case (iv) is complete.
Case (v). n = 2 (mod 4) and m is even.
(2.8) has two solutions in Zm, namely f = (e + 1)n/4 or f = (e + 1)n/4 + m/2. It remains to show e2 = 1 (mod 2m). By substitution of f into (2.4) we get
(e2 - 1)n/4 = 0 (mod m).	(2.11)
By the assumption, we may set m = 2r m0 where r > 1 and m0 is odd. A combination of (2.2) and (2.11) yields the system
ie2 - 1 = 0 (mod 2rm0), je2 - 1 = 0 (mod 2r+1(m0/h)),
where h = gcd(m,n/2). By the assumption, n/2 is odd, so h = gcd(m0,n/2). By the Chinese Remainder Theorem, the above system is equivalent to the system
ie2 - 1 = 0 (mod 2r+1), le2 - 1 = 0 (mod m0).
We now apply the Chinese Remainder Theorem once again and get e2 = 1 (mod 2m). This completes Case (v) as well as the proof of Theorem 2.2.	□
The next corollary determines the basic parameters of the maps C(n, m; e, f). Recall that the type of a regular or orientably regular map M is the symbol {p, q} where p is the face-size and q is the vertex-valency of M.
Corollary 2.4. The map C (n, m; e, f) has type {nm/h, 2m} and its genus is n(m-1)/2 — (h — 1), where h = gcd(f, m).
Proof. To determine the type and the genus of C(n, m; e, f) we need to determine the order of the element xy. Since (xy)n = (x2)f and x2 has order m, we see that the order of xy is nm/h where h = gcd(f, m). It follows that the map has type {nm/h, 2m}. Since |G(n, m; e, f )| = 2mn, the numbers of vertices, edges, and faces of C(n, m; e, f) are n, mn, and 2h, respectively. Therefore, by the Euler-Poincare Formula, the map has genus n(m — 1)/2 — (h — 1), as claimed.	□
Remark 2.5. Let A(g) denote the order of a largest group of conformal automorphisms of a compact Riemann surface of genus g. Accola [1] and MacLachlan [17] independently proved that 8(g +1) < A(g) < 84(g — 1) for g > 2 and there are infinitely many integers g > 2 for which the equality A(g) = 8(g + 1) holds. If we take n = 4, e = —1, and f = 0 in Corollary 2.4, we get that the genus of C(4, m; —1,0) is g = m — 1 with the automorphism group G of order |G| = 8(g + 1), the lower bound of A(g).
186
Ars Math. Contemp. 8 (2015) 133-148
3 Non-orientable regular embeddings of C(m)
As in the orientable case, regular maps on non-orientable surfaces can be represented in a purely algebraic manner [12]. Every regular map M on a closed surface, and hence every regular map on a non-orientable surface, may be identified with a quadruple (G; l, r, t) where G is a finite group and {l,r, t} is a generating set for G with l2 = r2 = t2 = (lt)2 = 1, where the elements l, r, t and It are all nontrivial. Such a quadruple is called an algebraic regular map. Elements of G represent flags of M, pairwise incident triples of the form (v, e, f) where v is a vertex, e is an edge and f is a face of M. The right translations of G by l, r, and t correspond to the longitudinal, rotary, and the transversal involution of M, respectively. The longitudinal involution fixes e and f of each flag (v, e, f) while interchanging the end-vertices of e. The rotary involution fixes v and f of (v, e, f) while interchanging the two edges sharing the same corner of f at v. The transversal involution fixes v and e of (v, e, f) while interchanging the two faces incident with e. The vertices, edges, and faces of M are in a one-to-one correspondence with the letf cosets of the subgroups (r, t), (l, t), and (l, r), and the incidence between the objects corresponds to non-empty intersection of cosets.
Two algebraic maps (G; l,r, t) and (G; l', r',t') represent isomorphic regular maps if and only if there is an automorphism of G taking l to l', r to r', and t to t'. Each automorphism of the map M = (G; l, r, t) corresponds to a left translation g ^ ag, g G G, where a is a fixed element of G. In particular, the group Aut(M) of all automorphisms of M is isomorphic to G.
The underlying surface of a regular map (G; l, r, t) need not be non-orientable, nevertheless, the criterion of orientability is easy: a regular map (G; l, r, t) is orientable if and only if the even-word subgroup G+ = (rt, tl) has index 2 in G. Thus, if M = (G; l, r, t) is non-orientable, then G+ = G, and the triple M = (G; x, y) with x = rt and y = tl represents an orientably regular map such that Aut+ (M) = G = Aut(M). The orientably regular map M is known as the antipodal double cover over M; conversely, M is said to be a halved non-orientable quotient of M. An orientably regular map is called antipodal if it admits a halved non-orientable quotient.
Observe that the involution t G G plays the role of a reflection of M, since xl = x-1 and yf' = y-1 = y. In general, an inner reflection of an orientably regular map N = (G; x, y) is any element g G G satisfying the following conditions:
Orientably regular maps admitting inner reflections are called algebraically antipodal. It is proved in [20, Theorem 7.5] that an algebraically antipodal orientably regular map is antipodal with the exception of spherical dipole maps D(m, -1) where m is odd, their duals, and regular maps with a single vertex and valency at most 2. More precisely, if N = (G; x, y) is an orientably regular map and g is an inner reflection of N, then with the exception of the maps just mentioned, the map M = Ng = (G; xg, yg, g) is a halved quotient of N.
Although the antipodal double cover over a non-orientable regular map is uniquely determined, the same is not true for halved quotients: an antipodal regular map may have different halved quotients corresponding to different inner reflections [25]. However, con-
(3.1a) (3.1b) (3.1c)
K. Hu et al.: Regular embeddings of cycles with multiple edges revisited
187
ditions (3.1a)-(3.1c) imply that if g1 and are two inner reflections, then there exists a central involution z such that g2 = zg1. In particular, the number of inner reflections of an antipodal map equals the number of central involutions (including the identity).
Before moving on to the classification of non-orientable multicyclic regular maps it will be useful to recall that non-orientable regular maps with multiple edges occur in two varieties: either every pair of parallel edges forms an orientation-preserving cycle or there exists a pair of parallel edges forming an orientation-reversing cycle. By regularity, in the latter case every edge must be involved in such a cycle. Following [16], we call such maps Möbius regular maps. Möbius maps were earlier investigated by Wilson [27] under the name cantankerous maps. By using geometric arguments Wilson showed that the multiplicity of such a map must be 2 (see [27, p. 265] and also [16, Lemma 6]). For the sake of completeness we include a proof of this fact based on the determination of all non-orientable regular embeddings of dipoles.
Observe that the dipole D2 has exactly one non-orientable embedding, which is regular and its supporting surface is the projective plane. This embedding is isomorphic to the map (H; l, r, t) where H is the dihedral group of order 8 with presentation
H = (l, r, t | l2 = r2 = t2 = (lt)2 = 1, (rt)2 = 1, (lrt)2 = t).	(3.2)
The next lemma shows that there is no other non-orientable regular embedding of any dipole.
Lemma 3.1. There are no non-orientable regular embeddings of the dipole Dm except the unique embedding of D2 in the projective plane isomorphic to the map defined by the presentation (3.2).
Proof. It is clear that the dipole D2 has a unique embedding in the projective plane and that the embedding is regular. Now let M = (H; l, r, t) be a non-orientable regular embedding of Dm with m > 2. Since Dm has just two vertices, the subgroup D = (r, t) has index two in H. Clearly, D is dihedral of order 2m. If we set a = rt, then (a) < D and D = (a, t). Since D < H and D is dihedral, we get
lal = a®tj, where i e Zm and j e Z2.	(3.3)
Suppose that j = 0. From (3.3) we then deduce that a = l2al2 = a®2, proving that i2 = 1 (mod m). It follows that H has presentation
(a, t, l | am = l2 = t2 = (lt)2 = 1, tat = a-1, lal = a®).
However, it is straightforward to verify that the even-word subgroup H + = (rt, tl) = (a, lt) has index two in H, contradicting the assumption that M is non-orientable. Therefore j = 1. It follows that the element a®tj = a®t is an involution, and hence a is an involution as well. In particular, m = 2.
Now suppose that i = 0. Then (3.3) reduces to
lrlt lt=tl lrtl a=rt lal (3=3) t
VI VO - VI OV - VHiV — V ^
implying that r = 1, which is impossible. Therefore i = 1 and (3.3) reduces to the relation lal = at. Thus M is isomorphic to the previously defined embedding of D2 into the projective plane, and the proof is complete.	□
188
Ars Math. Contemp. 8 (2015) 133-148
The following result appears in [16] and [27]. We provide a purely algebraic proof.
Theorem 3.2. Let X be a simple graph of order at least 2 and of valency d. Then a regular embedding M = (G; l, r, t) of the graph X(m) with multiplicity m is a Mobius regular map if and only if m = 2 and the generators l, r and t satisfy the identity
(l(rt)d)2 = t.	(3.4)
Proof. Note that the action of the automorphism group G on the flags of M induces an action on the vertices and an action on the edges of M. We may therefore assume that the subgroup (r, t) of G fixes a vertex u, and the subgroup (l, t) fixes an edge joining the vertex u and an adjacent vertex v. Let H be the subgroup of G fixing the set {u, v}. Then H may be regarded as the automorphism group of a regular embedding H of the dipole Dm whose vertices are u and v and whose edges are the edges between u and v. The underlying graph structure implies that d is the smallest positive integer k such that the element (rt)k fixes both u and v. Therefore, H = (H; (rt)d, l, t).
If M is a Mobius regular map, then the regularity of M implies that H is also a Mobius regular map. By Lemma 3.1, m = 2 and the identity (3.4) holds. Conversely, if m = 2 and M satisfies the identity (3.4), then H is a non-orientable embedding of the 2-cycle C2. The definition of H implies that M contains an orientation reversing cycle, so M is Mobius regular map.	□
To formulate our classification theorem for non-orientable multicyclic regular maps we define two families of maps. First, let C(m, n) denote the non-orientable regular map (H(m, n); l, r, t) with H(m, n) being the group with presentation
(l, r, t | l2 = r2 = t2 = (tl)2 = (rt)2m = (rl)2n = (rtrl)2 = 1, (rt)m(rl)n = r), (3.5)
where n > 3 and m > 1 are odd integers. It is not difficult to see that the antipodal double cover of C(m, n) is the multicyclic orientably regular map C(2n, m, -1,0).
Second, let M(n) denote the non-orientable regular map (H(n); l,r, t) with H(n) being the group with presentation
(l, r, t | l2 = r2 = t2 = (tl)2 = (rt)4 = (rl)n = 1, (l(tr)2)2 = t), (3.6)
where n = 0 (mod 3). By Theorem 3.2, the relation (l(tr)2)2 = t in the above definition forces M (n) to be a Mobius map.
The following theorem is, except for the enumeration part, due to Li and Siran [15, Proposition 8]. Our proof is based on the classification of orientably regular embeddings of presented in the previous section and on Theorem 3.2 about Mobius maps proved above. The original proof of Li and Siran employed the analysis of regular maps with an unfaithful action of the map automorphism group on vertices.
Theorem 3.3. Let M be a non-orientable regular embedding of an m-fold n-cycle C^. Then either
(i)	m and n are both odd, and M is isomorphic to the map C(m, n), or
(ii)	m = 2, n = 0 (mod 3), and M is isomorphic to the Mobius map M(n).
K. Hu et al.: Regular embeddings of cycles with multiple edges revisited
189
Moreover, for each pair (n, m) of admissible integers there is a unique non-orientable regular embedding of c4m).
Proof. Let M = (G; l, r, t) be a non-orientable regular embedding of Cn \ and let M = (G; x, y) be the antipodal double cover of M, where x = rt and y = tl. We distinguish two cases.
Case (i). Every 2-cycle of M is orientation-preserving.
Since the antipodal cover is a smooth cover, the valency of M is preserved, and each set of m parallel edges in M lifts to a set of m parallel edges in Mi .So Mi is an orientably regular embedding of C^. By Theorem 2.2, Mi = (G; x, y), where
G = G(2n, m, e, f) = (x, y | x2m = y2 = 1, (x2)y = (x2)e, (xy)2n = (x2)f >, (3.7)
where the parameters 2n, m, e, and f satisfy the numerical conditions stated in Theorem 2.2. Let K = (x2 >. Then K < G and M /K = C2n, where C2n denotes the dihedral map of type {2n, 2} on the sphere. The inner reflection t of Mi projects onto the inner reflection t = (xy)n of C2n. It follows that t = x2k(xy)n for some k G Zm. Using the commuting rule
(x2)y = x2e	(3.8)
we get
x-1 (3^b) (x2k(xy)n)-1x(x2k(xy)n) (3=.=8) (xy)-nx(xy)n,	(3.9)
which implies
x-2 (==) (xy)-x2(xy)« (3=8) ( x2 if n is even	(3.10a)
I x2e if n is odd.	(3.10b)
Suppose that n is even. From (3.10a) we deduce that x4 = 1, so m = 2. Theorem 2.2 now implies that e = 1 and therefore
x-1 (3=9) (xy)-nx(xy)n = (yxx-2)nx(xy)n (3==8) x-2n+2(yx)2nx-1.	(3.11)
Since (xy)2n = x2f, we have (yx)2n = y-1((xy)2n)y = (x2f )y = x2ef x2f. If we combine this with (3.11), we get x-2n+2f +1 = 1. Consequently, —2n + 2f + 1 = 0 (mod 4), which cannot hold. It follows that n must be odd. By (3.10b), e = m — 1. We have
(3-1a) ,2 2k < \n 2k < \n (3-8K \2n (3-7) 2f 1 = t2 = x (xy)nx2k(xy)n = (xy)2n = x2f,
so f = 0. Moreover,
1 (3=c)(x2k (xy)n)-1y(x2k (xy)n)y = (yx-1)nx-2k y(x2k (xy)n)y
=(yxx-2)nx-4ky(xy)ny (3=8) x4k (yxx-2)n(yx)n (3.=8) x4k+2(yx)2n (3=)x4k+2x2/ = x4k+2.
190
Ars Math. Contemp. 8 (2015) 133-148
Since the order of x2 is m, we get 2k +1 = 0 (mod m), and hence k = (m — 1)/2. It can easily be verified that if both m and n are odd, then xm-1(xy)n is the unique inner reflection of the map C (2n, m; m — 1,0) that gives rise to a non-orientable regular embedding of C*im). Let t = xm-1(xy)n, r = xt and l = yt. Then, upon substitution, the group
G(2n, m; m — 1,0) receives the presentation (3.5), and hence M = C(m, n).
Case (ii). There exists an orientation-reversing 2-cycle in M.
By Theorem 3.2, m = 2, every 2-cycle is orientation-reversing, and M = (G; l, r, t) is a Mobius regular map. It follows that the antipodal double cover M = (G; rt, tl) of M is an orientably regular embedding of the lexicographic product Cn[K2], where each vertex w of M lifts to two vertices w0 and u1 which are antipodal points of M. Without loss of generality we may assume that the generator x = rt fixes a certain vertex w0 and that the generator y fixes an edge w0v0 incident with v0. Set a = x2, b = ay, and K = (a, b). Then K acts regularly on the darts (uj, Vj) where i, j G Z2 .By regularity, K = Z2 © Z2. We first show that K < G. It is evident that
ax = a, ay = b and by = a.	(3.12)
Notice that since w0 and w1 are antipodal points, x fixes both w0 and u1. Similarly, yxy fixes both v0 and v1. Using regularity again we see that yx2y interchanges w0 and w1. Therefore, for any dart of the form (wj, Vj) we get
bx(wj, Vj) = x-1yx2yx(wj, Vj) = x-1yx2y(wj, wfc) = x-1 (wi+1,wh) = (wi+1, vs),
where k, h, s G Z2 and w0 and w1 are vertices adjacent to w0 but distinct from v0 and v1. Thus bx G K and hence K < G.
Next we show that bx = ab. Since M is a halved quotient of M in which every pair of antipodal vertices w0 and w1 is identified to a single vertex w, there exists an inner reflection g which identifies the antipodal pairs. Notice that M/K = Cn, where Cn is the dihedral map of type {n, 2}. By regularity, g G K. From (3.1b) we see that g = 1 and g = a. If we had g = b, then from (3.1c) we would derive that by = b, which is a contradiction with the assumption by = a. Therefore g = ab = x2yx2y and consequently
xg = x2(yx2y)x(x2)(yx2y) (3=b) x-1. Since [x2, yx2y] = 1, we get
bx = x-1(yx2y)x = x-2yx2y = x2 yx2y = ab.	(3.13)
For convenience, set z = xy. Then zn G K, which implies that zn = ajbj for some i, j G Z2. From (3.12) and (3.13) we derive that
az = b, bz = ab, and (ab)z = a,	(3.14)
so ajV = zn = (zn)z = (ajbj)z (3^4) bj(ab)j = ajbi+j, and hence ai-j = bj. Since (a) n (b) = 1, we see that i = 0 and j = 0. Therefore, zn = 1. Observe that the action of z on K defined by (3.14) induces the permutation (1)(a, b, ab), which implies that n = 0 (mod 3). Moreover, since
zy = (xy)y = yx = yx 1x2 = (xy) 1x2 = z 1a,
(3.15)
K. Hu et al.: Regular embeddings of cycles with multiple edges revisited
191
we get G = (a, b, z, y) = (K x (z)) x (y). Therefore G is defined by the presentation
(x,y | a = x2,b = ay, x4 = y2 = [a, b] = (xy)n = 1, bx = ab). (3.16)
Conversely, It is straightforward to verify the group given by (3.16) with n = 0 (mod 3) gives rise to an orientably regular embedding of the graph Cn [K2].
To complete the proof it remains to show that t = ab is a unique inner reflection giving rise to a halved quotient with a multicyclic underlying graph. Let Ic(G) denote the subgroup of G generated by all its central involutions. From the previous part of the proof we know that G/K is isomorphic to the dihedral group of order 2n. If g e Ic(G), then gK e Z(G/K). Since
Z (G/K )
1, n is odd,
(zn/2), n is even,
there exist elements i,j, k e Z2 such that g = albj if n is odd, and g = albj(zn/2)k if n is even.
If n is odd, then albj = g = gy = (albj)y = ajbl. Since (a) n (b) = 1, we have i = j. Moreover, we have albl = g = gz = (albl)z = alb21 = al, so i = 0 and hence Ic(G) = 1.
Now we assume n is even. Recall that n = 0 (mod 3). We deduce from (3.14) that [a, zn/2] = [b, zn/2] = 1, and from (3.15) that [y, zn/2] = 1. So zn/2 e Ic(G). Applying similar techniques we may deduce that if an element h = albj belongs to Ic(G), then h =1. Therefore, Ic(G) = (zn/2).
Summing up, we have proved that if n is odd, there is a unique inner reflection ab, and if n is even, there are two inner reflections ab and abzn/2. However, the latter inner reflection does not produce an embedding of Cnm). If we set t = ab, r = xt, and l = yt, then the presentation (3.16) transforms to the presentation (3.5). In either case, the antipodal regular covering that projects onto a non-orientable regular embedding of C(m) is unique, so for each pair (n, m) of admissible integers there is a unique non-orientable regular embedding of C(m), as claimed.	□
As a corollary to the main theorem of this section we present a strengthening of a result due to Wilson [26] about non-orientable regular maps whose number of edges is a power of 2. Our result features two infinite classes of projective-planar regular maps arising as halved quotients of dihedral spherical maps: a unique embedding of the cycle Cn of length n > 1 in the projective plane which is a halved quotient of the map C2n, and its dual, the balanced embedding of the bouquet of n loops in the projective plane which is the halved quotient of the dipole map D(2n, -1).
Theorem 3.4. If M is a regular map with nilpotent automorphism group, then Aut(M) is a 2-group. Furthermore, if M is non-orientable, then M is either the balanced embedding of the bouquet of 2n loops into the projective plane for some n > 0 or its dual, a projective-planar embedding of the cycle C2n.
Proof. Let M = (G; l,r,t) be a regular map where G is nilpotent. Then G can be expressed as a direct product H x K where H is a 2-group and K has odd order. The elements l, r, and t belong to H, because they are involutions. It follows that H = G and K = 1. In other words, G is a 2-group.
192
Ars Math. Contemp. 8 (2015) 133-148
Now assume that M = (G; i, r, t) is non-orientable. Since G is a 2-group, M has 2n edges for some n > 0 and hence |G| = 2n+2. We proceed by induction on n to show that M is either the balanced embedding of the bouquet of 2n loops into the projective plane with n > 0 or its dual.
An easy check of non-orientable regular maps with at most four edges shows that the claim is true for n < 2. For the induction step assume that the statement holds for some n > 2 and let M = (G; i, r, t) be a non-orientable regular map with 2n+1 edges, so that |G| = 2n+3. Since G isa 2-group, it has a non-trivial centre, and hence it contains a central involution z = 1. Clearly, (z) < G, so we may construct the quotient map M = (G; I, f, f) where G = G/(z) and I, f, and f are the images of r, i, and t, respectively. By the induction hypothesis, M is either an embedding of the cycle C2n into the projective plane or its dual. We may clearly assume that M is an embedded cycle. Then G has a presentation
G = (i, f, f | f2 = f2 = t2 = (if)2 = 1, (ff)2 = (ff)2n = 1).
Since G is a cyclic central extension of G by (z), we get
G = (i,r,t | i2 = r2 = t2 = (it)2 = 1, (rt)2 = z\ (ri)2" = zj),
for some i, j G Z2. If i = 0, then j = 1, and M is an embedding of C2n+i into the projective plane. If i = 1, then since it(rt)2it = z = (rt)2, the underlying graph of M is a cycle with multiplicity 2, which violates Theorem 3.3. This establishes the induction step, and the proof is complete.	□
Remark 3.5. Breda d'Azevedo, Nedela, and Sirffl [3] showed that for any integer p = 7 (mod 12) with p > 7 the groups
Gj,i = (r, s | x2j = s21 = (rs)2 = (rs-1)2 = 1),
where j > i > 3 and (j - 1)(i - 1) = p +1 give rise to infinitely many non-orientable regular maps of Euler characteristic -p. If p is a prime, this family forms a complete set of regular maps on the non-orientable surface of Euler characteristic -p. After setting i = m and j = n it becomes clear that these maps are identical with regular embeddings of Cim) defined by (3.5).
Remark 3.6. Malnic, Nedela, and Skoviera [18] proved that if the automorphism group of an orientably regular map M is nilpotent, then M can be decomposed into a direct product of two orientably regular maps, an orientably regular map whose automorphism group is a 2-group and a semistar of odd valency [18, Theorem 3.2]. Since the automorphism group of every non-orientable regular map is also the automorphism group of its antipodal double cover, it follows from Theorem 3.4 that no orientably regular maps with nilpotent automorphism groups are antipodal, except the dihedral maps {2n, 2} on the sphere and their duals.
Acknowledgements
Our research received support from the following grants: "Mobility - Enhancing Research, Science and Education" at Matej Bel University in Banska Bystrica, ITMS code 26110230082, under the Operational Programme Education co-financed by the European
K. Hu et al.: Regular embeddings of cycles with multiple edges revisited
193
Social Fund, APVV-0223-10, VEGA 1/1085/11, VEGA 1/1005/12, by the EUROCORES Programme EUROGIGA (Project GReGAS) of the European Science Foundation under the contract APVV-ESF-EC-0009-10, and by the Slovak-Chinese bilateral grant APVV-SK-CN-0009-12.
References
[1]	R.D.M. Accola, On the number of automorphisms of a closed Riemann surface, Trans. Amer. Math. Soc. 131 (1968), 398-408.
[2]	H.R. Brahana, Regular maps and their groups, Amer J. Math. 41 (1927), 268-284.
[3]	A. Breda d'Azevedo, R. Nedela and J. Siran, Classification of regular maps of negative prime Euler characteristic, Trans. Amer Math. Soc. 357 (2005), 4175-4190.
[4]	D.A. Catalano, M. D. E. Conder, S.-F. Du, Y. S. Kwon, R. Nedela and S. Wilson, Classification of regular embeddings of n-dimensional cubes, J. Algebraic Combin., 33 (2011), 215-238.
[5]	H.M.S. Coxeter and W.O.J. Moser, Genarators and Relations for Discrete Groups, Berlin, New York, Springer-Verlag, 1972.
[6]	S.-F. Du, J. H. Kwak and R. Nedela, Regular embeddings of complete multipartite graphs, European J. Combin. 26 (2005), 505-519.
[7]	A. Gardiner, R. Nedela, J. Siran and M. Skoviera, Characterisation of graphs which underlie regular maps on closed surfaces, J. London Math. Soc. 59 (1999), 100-108.
[8]	L.D. James, Imbeddings of the complete graph, Ars Combin. 16-B (1983), 57-72.
[9]	L.D. James and G.A. Jones, Regular orientable imbeddings of complete graphs, J. Combin. Theory Ser. B 39 (1985), 353-367.
[10]	G.A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. 37 (1978), 273-307.
[11]	G.A. Jones, Regular embeddings of complete bipartite graphs: classification and enumeration, Proc. London Math. Soc. 101 (2010), 427-453.
[12]	G.A. Jones and J.S. Thornton, Operations on maps, and outer automorphisms, J. Combin. Theory Ser. B 35 (1983), 93-103 .
[13]	Y.S. Kwon, New regular embeddings of n-cubes Qn, J. Graph Theory 46 (2004), 297-312.
[14]	Y.S. Kwon and R. Nedela, Non-existence of nonorientable regular embeddings of n-dimen-sional cubes, Discrete Math. 307 (3-5) (2007), 511-516.
[15]	C.H. Li and J. Siran, Regular maps whose groups do not act faithfully on vertices, edges, or faces, European J. Combin. 26 (2005), 521-541.
[16]	C.H. Li and J. Siran, Mobius regular maps, J. Combin. Theory Ser. B 97 (2007), 57-73.
[17]	C. MacLachlan, A bound for the number of automorphisms of a compact Riemann surface, J. London Math. Soc. 44 (1969), 265-272.
[18]	A. Malnic, R. Nedela, and M. Skoviera, Regular maps with nilpotent automorphism groups, European J. Combin. 33 (2012), 1974-1986.
[19]	R. Nedela and M. Skoviera, Regular maps of canonical double coverings of graphs. J. Combin. Theory Ser. B 67 (1996), 249-277.
[20]	R. Nedela and M. Skoviera, Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997), 807-823.
[21]	R. Nedela and M. Skoviera, Exponents of orientable maps, Proc. London Math. Soc. 75 (1997), 1-31.
194
Ars Math. Contemp. 8 (2015) 133-148
[22]	R. Nedela, M. Skoviera and A. Zlatos, Regular embeddings of cycles with multiple edges, manuscript (2001).
[23]	M. Skoviera and A. Zlatos, Regular maps with multiple edges on orientable surfaces, manuscript (2000).
[24]	W. Threlfall, Gruppenbilder, Abh. sachs. Akad. Wiss. Math.-phys. Kl. 41 (1932), 1-59.
[25]	S.E. Wilson, Non-orientable regular maps, Ars Combin. 5 (1978), 213-218.
[26]	S.E. Wilson, Bicontactual regular maps, Pacific J. Math. 120 (1985), 437-451.
[27]	S.E. Wilson, Cantankerous maps and rotary embeddings of Kn, J. Combin. Theory Ser. B 47 (3)(1989), 262-279.
[28]	H. Zassenhaus, The Theory of Groups, Chelsea Publishing Co., New York, 1949.
[29]	J.-Y. Zhang and S.-F. Du, On the orientable regular embeddings of complete multipartite graphs, European J. Combin. 33 (2012), 1303-1312.