ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.01
https://doi.org/10.26493/1855-3974.2408.42e
(Also available at http://amc-journal.eu)
Generalized Cayley maps and their Petrie duals*
Robert Jajcay †
Comenius University, Bratislava, Slovakia
Jozef Širáň ‡
Slovak University of Technology, Bratislava, Slovakia
Yan Wang §
Yan Tai University, Yan Tai, China
Received 12 August 2020, accepted 22 October 2023, published online 6 June 2024
Abstract
Cayley maps are embeddings of Cayley graphs in orientable surfaces which possess a
group of orientation preserving automorphisms acting regularly on the vertices. We gen-
eralize the concept of a Cayley map by considering embeddings of Cayley graphs in both
orientable and non-orientable surfaces and by requiring a group of automorphisms acting
regularly on vertices that does not have to consist entirely of orientation preserving auto-
morphisms. This leads to new families of maps in both the orientable and non-orientable
cases. Since the Petrie dual operator preserves the property of being a generalized Cayley
map, throughout the paper we consider the action of this operator on our maps.
Keywords: Cayley map, regular embedding, automorphism group of a map.
Math. Subj. Class. (2020): 05C10, 05C25, 05E18
*We wish to thank our referees for their repeated careful readings of our article and their helpful and knowl-
edgeable suggestions that helped considerably in improving our article and making it more focused.
†Corresponding author. Supported by VEGA Research Grant 1/0437/23 and APVV Research Grant 19-0308.
‡Supported by APVV Research Grants 19-0308 and 22-0005, and VEGA Research Grants 1/0567/22 and
1/0069/23.
§Supported by NSFS No. ZR2020MA044.
E-mail addresses: robert.jajcay@fmph.uniba.sk (Robert Jajcay), jozef.siran@stuba.sk (Jozef Širáň),
wang−yan@pku.org.cn (Yan Wang)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P3.01
1 Introduction
A map is a cellular embedding of a connected graph on some surface; the map is orientable
if the surface is. By a widely adopted definition (cf. [16]), an orientable map M is a Cayley
map if the group of orientation-preserving automorphisms of M contains a subgroup acting
regularly on the vertex set of M. This way of introducing Cayley maps has been motivated
by Sabidussi’s well known characterization of Cayley graphs in terms of a subgroup of
automorphisms of the graph acting regularly on its vertex set [18]. Apart from the history
of the development of the theory of maps, however, when carrying Sabidussi’s characteri-
zation over to maps there is no reason to restrict to orientation-preserving automorphisms,
or even to orientable surfaces. The latter may have been first realized by Tucker [19], and
in this paper we argue for the return of his way of treating Cayley maps.
In order not to clash with customary terminology we will say that a map M on an
arbitrary surface (orientable or not) is a generalized Cayley map if the automorphism group
of M contains a subgroup H that is a regular permutation group on the vertex set of M.
In our view, Tucker’s definition by means of existence of a regular action of a group of
automorphisms has two major advantages: it is a generalization of the currently used defi-
nition that is simple, and in line with the original definition of a Cayley map. To the best of
our knowledge there have been two other attempts at defining non-orientable Cayley maps:
the one by Abas [1] via strategically placed cross-cups on the carrier surface, and another
one by Kwak and Kwon [12] who developed a full theory of generalized Cayley maps
(equivalent to Tucker’s and our approach) but starting off from introducing generalized
Cayley maps in a way that appears to be hard to use in applications.
The main difference between (original and orientable) Cayley maps and generalized
Cayley maps is that the carrier surfaces of the latter may be non-orientable, and even in
the orientable case the subgroup required to act regularly on vertices does not have to be
orientation-preserving. Maps admitting such subgroups appear frequently in the context of
regular maps with automorphism groups acting quasi-primitively on the vertices [6], and
our study of such maps was the main source of motivation for the present paper.
At several places, we employ the Petrie dual operator (e.g., [22]) which proves par-
ticularly useful since it preserves the class of generalized Cayley maps. For example, we
consider orientable generalized Cayley maps whose Petrie dual is again an orientable gen-
eralized Cayley map, as well as non-orientable generalized Cayley maps whose Petrie dual
is orientable.
The outline of the paper is as follows. In order to emphasize parallels between the
original Cayley maps on orientable surfaces and the generalized Cayley maps, the three
sections following this Introduction are devoted to reviewing the background and context
of highly symmetric maps, Cayley maps, and the Petrie dual operator; with Sections 5 and 6
containing the new results. We begin in Section 2 by reviewing some of the most important
properties of regular maps, followed in Section 3 by reviewing algebraic machinery for
dealing with orientable Cayley maps in their original setting. Section 4 discusses Petrie
duals of maps in some detail. We discuss generalized Cayley maps on orientable surfaces
in Section 5 and generalized Cayley maps on non-orientable surfaces in Section 6.
We can summarize the results obtained in our paper as follows. A generalized Cayley
map may be both orientable and non-orientable. The orientable generalized Cayley maps
come in two kinds. First, there are the original orientable Cayley maps in which the group
acting regularly on the vertices of the map consists entirely of orientation preserving auto-
morphisms. Then there are orientable generalized Cayley maps with bipartite underlying
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 3
graphs in which the group acting regularly on the vertices of the map contains a subgroup
of index 2 consisting of orientation preserving automorphisms while the other half of the
regularly acting group consists of orientation reversing automorphisms (Theorems 5.1 and
5.2). There are infinitely many examples of orientable generalized Cayley maps which
are not the original Cayley maps (Lemma 5.3 and Example 5.5), and infinitely many ori-
entable generalized Cayley maps which are self-Petrie-dual (Remark 5.6). In Remark 5.7
we present orientable generalized Cayley maps that simultaneously admit an orientation
preserving group acting regularly on their vertices and a vertex-regular group half of which
consists of orientation reversing automorphisms (hence, these maps are classical Cayley
maps and orientable maps of the second kind at the same time).
In Remark 6.2 we present an infinite family of non-orientable generalized Cayley maps.
Taking advantage of the well-known fact that the Petrie dual of an orientable map M
is orientable if and only if the underlying graph of M is bipartite (Theorem 4.2 in our
paper), we argue the existence of infinitely many examples of the original orientable Cayley
maps whose Petrie duals are orientable (Example 6.6) and infinitely many examples of
the original orientable Cayley maps whose Petrie duals are non-orientable (any orientable
Cayley map with a non-bipartite underlying graph). The Petrie dual of a non-orientable
generalized Cayley map may be both orientable and non-orientable. We classify the non-
orientable generalized Cayley maps whose Petrie dual is orientable (Corollary 6.5) and
exhibit infinitely many examples of both non-orientable generalized Cayley maps whose
Petrie dual is orientable and non-orientable generalized Cayley maps whose Petrie dual is
non-orientable (Remark 6.2).
2 Regular, orientably-regular, reflexible and chiral maps
For a map M, regions (faces) of its barycentric subdivision are the flags of the map. Every
flag is a triangular region; informally, its three ‘corners’ are a vertex, the ‘midpoint’ of an
edge incident with the vertex, and the ‘centre’ of a face incident with both the vertex and the
edge. As long as no face of the map contains two occurrences of an edge on its boundary
(no maps with such a degeneracy will be considered here), a flag can be identified with a
triple (v, e, F ), where v is a vertex, e an edge incident with v, and F is a face incident with
both v and e. A pair of distinct flags (v, e, F ) and (v′, e′, F ′) of M are incident if they
share a segment of the skeleton of the barycentric subdivision; in case when no face of the
map contains two occurrences of an edge on its boundary, two flags are incident if precisely
two of the three equalities v = v′, e = e′, F = F ′ hold.
Let r0, r1 and r2 be involutory fixed-point-free permutations of the flag set of a map
M formed by two-cycles consisting of incident flags, with r0 swapping faces that share
a face-center-to-edge-midpoint segment, r1 swapping faces that share the vertex-to-face-
center segment, and r2 swapping faces that share the vertex-to-edge-midpoint segment;
again, if no face of the map contains two occurrences of an edge on its boundary, the flag
(v, e, F ) is mapped by r0 to (v′, e, f), v ̸= v′, by r1 to (v, e′, F ), e′ ̸= e, and by r2 to
(v, e, F ′), F ′ ̸= F . The (flag-transitive) permutation group generated by r0, r1 and r2 is
the monodromy group Mon(M) of the map. The three generators of the monodromy group
can be interpreted as ‘gluing instructions’ to assemble the map from its set of flags; in other
words, knowledge of Mon(M) in terms of the action of the generators r0, r1 and r2 on the
set its flags is equivalent to knowing the map M. Note that r0 and r2 commute; if the map
is finite, then the orders of r0r1 and r1r2 are equal to the least common multiples of face
4 Ars Math. Contemp. 24 (2024) #P3.01
lengths and vertex valencies, respectively.
It is well known that the carrier surface of M is orientable if and only if ⟨r1r2, r0r2⟩ =
⟨r1r2, r0r1⟩ is a subgroup of index 2 in Mon(M). In such a case we speak about an
orientable map; letting ρ = r1r2 and λ = r0r2 one may consider the ‘orientable part’
Mon+(M) = ⟨ρ, λ⟩, the index-2-subgroup of Mon(M). Here, Mon+(M) can be re-
garded as a permutation group acting on the dart set D of the map (i.e., on the set of
directed edges of the map). Then ρ is a permutation that cyclically permutes, at each vertex
v, the darts emanating from v in accord with a chosen orientation of the carrier surface of
the map, and λ is an an involution interchanging the two darts belonging to the same edge.
An automorphism of a map M with monodromy group Mon(M) = ⟨r0, r1, r2⟩ is
any permutation of the flag set F of M that preserves incidence of flags. Equivalently, a
permutation of F is an automorphism of M if and only if it commutes with all of r0, r1
and r2; hence the automorphism group Aut(M) of the map is simply the centralizer of the
monodromy group Mon(M) in the symmetric group SF on the set F . Since Mon(M) is
transitive on F , it follows that Aut(M) acts freely on the set set F .
For an orientable analogue, let now M be an orientable map with dart set D and with
Mon+(M) = ⟨ρ, λ⟩ being a subgroup of Mon(M) of index 2. An orientation-preserving
automorphism of M is any permutation of D commuting with ρ and λ. It follows that the
group Aut+(M) of all orientation-preserving automorphisms of an orientable map is the
centralizer of Mon+(M) in the symmetric group SD on the set D. Again, transitivity of
Mon+(M) on D implies that the group Aut+(M) acts freely on the set D. If such an
orientable map M admits an automorphism commuting with λ but inverting ρ, then the
automorphism is orientation-reversing.
Finally, let us discuss the highest ‘level of symmetry’of maps. A map M with mon-
odromy group Mon(M) is called regular if the automorphism group M acts regularly
on the set F of flags. In this case, the groups Aut(M) and Mon(M) are abstractly iso-
morphic, so that in the case of a finite map the order of both groups is equal to |F|. If
M is a regular orientable map, then its automorphism group Aut(M) contains the group
Aut+(M) of orientation-preserving automorphisms as a subgroup of index 2, its other
coset in Aut(M) being the collection of all orientation-reversing automorphisms of the
map. The orientation-reversing automorphisms are sometimes referred to as reflections,
giving such maps the name reflexible. An orientable map M is orientably-regular if the
group Aut+(M) of orientation preserving automorphisms of M acts regularly on its set
of darts. An orientably regular map that is not reflexible is chiral, and in such a case
Aut(M) = Aut+(M).
3 Cayley maps
A Cayley map is an orientable map M that admits a group of orientation preserving auto-
morphisms G acting regularly on its set of vertices. To make this definition more precise,
one needs to consider the induced action of map automorphisms of M on the vertex set
of the underlying graph associating the map automorphism ψ with the vertex permutation
ψ mapping v to v′ whenever ψ(v, e, F ) = (v′, e′, F ′). It is easy to see that ψ is a well
defined graph automorphism of the underlying graph of M defined via its action on the
vertices (of the map or the graph). The induced action of Aut(M) on the vertices is almost
universally faithful; with the very few exceptions listed in [14, Proposition 9]. The auto-
morphisms contained in the automorphism group of a Cayley map which acts regularly on
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 5
the vertices of the map correspond in this way to automorphisms of its underlying graph
forming a group acting regularly on the graph’s vertices, making it into a Cayley graph [18].
A Cayley graph C(G,X) is a graph whose vertex set can be identified with the elements
of a group G generated by a set X closed under taking inverses and not containing the
identity 1G, with the pairs of adjacent vertices consisting of all pairs g, gx with g ∈ G and
x ∈ X . A graph Γ is isomorphic to a Cayley graph C(G,X) if and only if AutΓ contains
a subgroup G acting regularly on the vertices of Γ [18], which justifies the remark we have
made about the underlying graphs of Cayley maps being Cayley. Hence, the automorphism
group of a Cayley map M containing a group G of orientation preserving automorphisms
acting regularly on the vertices of M is necessarily contained in the automorphism group
of its underlying Cayley graph C(G,X), G ≤ AutC(G,X) (after applying the necessary
restriction to vertices). The action of G on C(G,X) is defined for each g ∈ G via left
multiplication: Ag(h) = gh for all g, h ∈ H , and we shall denote the group {Ag | g ∈ G}
byGL; it is always a subgroup of AutC(G,X). The set of darts of the Cayley map M thus
takes the form {(h, hx) | h ∈ G, x ∈ X} and each Ag ∈ GL ‘extends’ to a permutation
of the darts of M mapping the dart (h, hx) to (gh, ghx). If each of the extensions of Ag ,
g ∈ G, is to preserve the orientation of M, there must exist a cyclic permutation p of X
having the property that the dart (g, gp(x)) is always the dart lying immediately next to the
dart (g, gx) in the local surface neighborhood of g (sharing the face with (g, gx)), for all
g ∈ G and x ∈ X [16]. Thus, we can talk about the local permutation of the darts (g, gx),
x ∈ X , emanating from g, determined by the cyclic permutation p of X . This gives rise
to an equivalent definition of a Cayley map as an orientable embedding of a Cayley graph
C(G,X) in an orientable surface determined by the local rotation scheme with the property
that the local surface ordering corresponding to the vertex g ∈ G, ρg , acting cyclically on
the darts (g, x), x ∈ X , does not depend on g, and is determined by a fixed cyclic permu-
tation p of X . Such Cayley map is denoted by CM(G,X, p), and the equivalence of this
‘local rotation definition’ and the definition via the existence of an orientation preserving
automorphism group acting regularly on its vertices is a well established fact in the theory
of Cayley maps [16].
As argued above, the group GL = {Ag | g ∈ G} (isomorphic to G) is always a
subgroup of the group Aut+CM(G,X, p) of orientation preserving automorphisms, and
CM(G,X, p) is orientably regular if and only if there exists an orientation preserving
automorphism A ∈ Aut+CM(G,X, p) which fixes the identity 1G and maps the darts
emanating from 1G in the same order as p: A((1G, x)) = (1G, p(x)), for all x ∈ X . This
has been shown to be equivalent to the existence a special identity-fixing permutation φ
called skew-morphism in [7], where it was first defined. Given a group G, a permutation
φ : G → G of the elements of G that fixes the identity of G, φ(1G) = 1G, is said to be a
skew-morphism of G with associated power function π : G→ N if the equation
φ(gh) = φ(g)φπ(g)(h) (3.1)
is satisfied for all g, h ∈ G. A Cayley map CM(G,X, p) is orientably regular if and
only if there exists a skew-morphism φ of G with the property φ(x) = p(x), for all
x ∈ X . Furthermore, a group G admits the existence of an orientably regular Cayley
map CM(G,X, p) if and only if G admits the existence of a skew-morphism φ with an
orbit X that generates G and is closed under taking inverses (in which case, the desired
orientably regular map is the map CM(G,X,φ|X)) [7]. The classification of finite groups
G that admit the existence of an orientably regular Cayley map CM(G,X, p) is a hard
6 Ars Math. Contemp. 24 (2024) #P3.01
problem and the topic of many articles. The orientation preserving automorphism group of
an orientably regular Cayley map with skew-morphism φ and power function π takes the
form Aut+(CM(G,X, p)) ∼= GL ⟨φ⟩ with the product multiplication defined by the rule
aφ = φπ(a)φ(a),
for all a ∈ G. A Cayley map CM(G,X, p) with the property p(x−1) = (p(x))−1 satisfied
by all x ∈ X is called a balanced Cayley map. Since a map CM(G,X, p) is balanced
if and only GL is normal in Aut+(CM(G,X, p)), we will break with the long line of
tradition, and we will call such map a normal Cayley map. This is in line with the name
given to Cayley graphs C(G,X) with GL normal in AutC(G,X).
Let us complete this section with a necessary condition for a Cayley map to be regular.
Even though it can be deduced from [5] and [7], we are not aware of this condition being
stated explicitly before, and so we also provide a short proof.
Theorem 3.1. If a Cayley map M = CM(G,X, p) is regular, there exists a pair of skew-
morphisms φ,ψ of G that preserve X and the restriction of φ to X is equal to p, while the
restriction of ψ to X is equal to p−1.
Proof. If M = CM(G,X, p) is regular, it is also orientably regular, hence there exists
a skew-morphism φ of G that preserves X and whose restriction to X is equal to p [7].
Moreover, if M is regular, it is isomorphic to its mirror reflection CM(G,X, p−1), which
is therefore also regular, hence orientably regular, and there exists a skew-morphism ψ of
G that preserves X and whose restriction to X is equal to p−1.
It is interesting to point out that the above necessary condition is not sufficient. For
example, the skew-morphism whose existence guarantees the orientable regularity of a
normal Cayley map CM(G,X, p) is well-known to be a group automorphism of G [21].
The inverse of a group automorphism is always a group automorphism, and hence a skew-
morphism. Thus, every orientably regular normal Cayley map admits a skew-morphism
whose restriction to X is p and whose inverse is a skew-morphism (and its restriction to X
is p−1). However, not every normal orientably regular Cayley map is regular. To mention
just one famous example, all orientably regular embeddings of complete graphs have been
shown to be normal Cayley maps, however, the only orientably regular embeddings of
complete graphs which are also regular are the orientable embeddings of complete graphs
of prime power order not exceeding 4 [8].
4 Petrie dual
The well-known duality operation switching the roles of vertices and faces of a map M
preserves some of the most important topological characteristics of M, such as the ori-
entability and the genus, but generally changes the underlying graph of M. The less well-
known Petrie duality has the advantage of preserving both the embedded graph and the
action of Aut(M) on it. This makes the Petrie dual operation more useful when dealing
with maps with automorphism groups acting regularly on vertices of the underlying graph.
The Petrie dual of a map M is the map P (M) with the same vertices and edges as M
(and thus, the same underlying graph), however, the faces of P (M) are determined by the
Petrie (or zig-zag) walks of M which visit vertices of M along the edges while switching
sides (i.e., faces) in the middle of every next edge situated along the boundary of the face
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 7
of M. The key point of our interest in the Petrie dual lies in the fact that the two maps
M and P (M) have the same vertex set and the same automorphism group. To put this
claim on a more precise footing, we turn again to the monodromy groups. If ⟨r0, r1, r2⟩ is
the monodromy group of a map M, the monodromy group of the Petrie dual P (M) is the
group ⟨r0r2, r1, r2⟩ (which can be easily seen from the fact that the two flags associated
with the opposite dart get swapped in the Petrie dual construction). Thus, P (P (M)) = M,
and, since ⟨r0, r1, r2⟩ = ⟨r0r2, r1, r2⟩, we obtain
Aut(M) = CSF (⟨r0, r1, r2⟩) = CSF (⟨r0r2, r1, r2⟩) = AutP (M).
Therefore, the two automorphism groups act on the same set of flags in exactly the same
way, and any properties of the automorphism group of M with regard to the vertices of
M are shared by the automorphism group of P (M). In particular, if Aut(M) contains a
subgroup acting regularly on the set of vertices of M, so does the group AutP (M). Since
we make repeated use of this observation throughout our paper, we state it in the form of a
theorem.
Theorem 4.1. A map M is a generalized Cayley map if and only if its Petrie dual P (M)
is also a generalized Cayley map.
Even though the Petrie dual pair shares with the original map the same underlying graph
and the same automorphism group, the two maps have usually quite distinct topological
properties. It is, for example, possible (even common) that M is orientable while P (M)
need not be. For an example, consider M to be the tetrahedron as an embedding of K4 on
the sphere. Then P (M) is an embedding of K4 in the projective plane as a map of type
{4, 3}.
Since we will have to be able to distinguish between various situations with regard to
the orientablity vs. non-orientability, we recall the following well-known result (e.g., [15,
Remark 7]).
Theorem 4.2. If M is orientable, then P (M) is orientable if and only if the underlying
graph of M is bipartite.
Next, recall the concept of a ribbon graph which is constructed from a map M by
cutting out an open neighborhood of each face-center and keeping small bands around the
edges of M and small circles around the vertices. The ribbon graph of the Petrie dual of
an orientable embedding of a bipartite graph is the ribbon graph of the original embedding
with all bands twisted (cut off at one of the end vertices and glued back after being rotated
by 180 degrees) [4].
Remark 4.3. There is a large number of examples of Cayley maps throughout the litera-
ture. For example, four of the five Platonic solids (all but the dodecahedron) are Cayley
maps. All orientably regular embeddings of complete graphs are also Cayley maps [8].
Since none of the complete graphs butK2 are bipartite, their Petrie duals are non-orientable
generalized Cayley maps.
On the other hand, the underlying graph of the dodecahedron is not a Cayley graph,
and hence the dodecahedron and its Petrie dual are neither Cayley maps nor generalized
Cayley maps.
8 Ars Math. Contemp. 24 (2024) #P3.01
5 Orientable generalized Cayley maps and their Petrie duals
Let us begin by pointing out that the underlying graph of any generalized Cayley map
(orientable or not) is a Cayley graph. This observation follows from the same line of
arguments as that included in our section on Cayley maps, namely, it follows from the fact
that the group of automorphisms of the underlying graph induced by the group G of map
automorphisms acting regularly on the vertices of the map acts regularly on the vertices
of the graph. Thus, as is well-known, the set of vertices of the underlying graph of a
generalized Cayley map can be identified with the elements of G, and the action of these
automorphisms on the elements of G is that of left-multiplication in G.
It follows that generalized Cayley maps M are precisely embeddings of Cayley graphs
C(G,X) into (orientable or non-orientable) surfaces satisfying the property that all left
multiplications in G viewed as permutations of the elements of G ‘extend’ into automor-
phisms of the embedding, and that the order of the automorphism group of M acting
regularly on the vertices of M must be equal to its number of vertices, i.e., must be equal
to |G|.
Thus, orientable generalized Cayley maps come in two kinds. First, there are the em-
beddings M of Cayley graphs C(G,X) in orientable surfaces having the property that all
left multiplications in G extend into orientation preserving automorphisms of M, which
are precisely the classical Cayley maps M = CM(G,X, p) [16]. An orientable general-
ized Cayley map M that is not of this kind, i.e., that is not a Cayley map, must then be an
embedding of a Cayley graph C(G,X) in an orientable surface having the property that at
least one of the left multiplications in G extends to an orientation-reversing automorphism
of M. Recall that any automorphism group of an orientable map that contains at least
one orientation reversing automorphism must contain an index 2 subgroup of orientation
preserving automorphisms. This means that orientable generalized Cayley maps which are
not Cayley maps are embeddings of Cayley graphs C(G,X) in which a subgroup HL of
GL of index 2 extends into orientation preserving automorphisms and the other coset of
this subgroup in GL extends into orientation reversing automorphisms.
Recall that an orientable embedding of C(G,X) is determined by choosing a cyclic
permutation ρg of the elements in X for each g ∈ G. In the case of Cayley maps
CM(G,X, p), for every g ∈ G, the permutation ρg of the elements of X must be equal
to p. This, of course, cannot be the case for orientable generalized Cayley maps which are
not Cayley maps, i.e., there must exist elements f, g ∈ G such that ρf ̸= ρg . However, the
distribution of local rotations in orientable generalized Cayley maps which are not Cayley
maps is only slightly more complicated than that of Cayley maps. Namely, all such maps
are still determined by a single cyclic permutation p of X which becomes the local rotation
for the vertices contained in a subgroup H of index 2 in G and whose inverse p−1 becomes
the local rotation for the rest of them. We shall denote these maps by GCM(G,H,X, p)
and note that each such map is an orientable embedding of a Cayley graph C(G,X) having
the properties that H is a subgroup of index 2 in G, p is a cyclic permutation of X , and the
embedding of C(G,X) is determined by the local rotations ρh = p, for all h ∈ H , and
ρk = p
−1, for all k ∈ G \H .
Using the notation introduced above, we classify in the following theorem orientable
generalized Cayley maps in terms of their local orientations.
Theorem 5.1. Let M be an orientable generalized Cayley map. Then M is either a Cayley
map, M = CM(G,X, p), or a map M = GCM(G,H,X, p) defined above.
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 9
Conversely, everyCM(G,H,X, p), i.e., every orientable embedding of a Cayley graph
C(G,X) having the property that ρh = p, for all h ∈ H , whereH is a subgroup of index 2
in G and p is a cyclic permutation of X , and ρk = p−1, for all k ∈ G \H , is an orientable
generalized Cayley map.
Finally, the maps GCM(G,H,X, p) and GCM(G,H,X, p−1) are isomorphic.
Proof. Let M be an orientable generalized Cayley map that is not a Cayley map, let
G ≤ Aut(M) act regularly on the vertices of M , and identify the vertices of M with
the elements of G. Let H be the subgroup of index 2 in G of automorphisms preserv-
ing the orientation in M whose existence has been argued prior to the statement of this
theorem.
First, let h be an element of H . This means that the associated map automorphism Ah
mapping the darts (g, x), g ∈ G, x ∈ X , to the darts (hg, x) preserves the orientation
in M. It follows that Ahρ(g, x) = ρAh(g, x), for all g ∈ G and x ∈ X , and thus
(hg, ρg(x)) = (hg, ρhg(x)), for all g ∈ G and x ∈ X . Since multiplication by h preserves
H and its coset, the above identities yield that ρh = ρh′ , for all h, h′ ∈ H , and ρk = ρk′ ,
for all k, k′ ∈ G \H . Taking next an element k ∈ G \H , its corresponding automorphism
Ak reverses the orientation in M, and hence satisfies the identity Akρ = ρ−1Ak. Thus,
(kg, ρg(x)) = (kg, ρ
−1
kg (x)), for all g ∈ G and x ∈ X . It follows that ρg = ρ
−1
kg , for all
g ∈ G. If we denote the cyclic permutation of X assigned to the elements of H by p, using
the fact that the multiplication by k swaps H and its coset yields that the elements in G\H
are assigned the local permutation p−1. This completes the proof of the first statement of
our theorem.
The proof of the second part of the theorem is essentially the reverse of the above. If
one chooses the local orientations as described in the theorem, it is easy to see that left
multiplication by the elements of H preserves and left multiplication by the elements from
G \H reverses the orientation of the obtained map.
The veracity of the final statement of our theorem can be verified by showing that
the mapping φk defined on the set of darts of GCM(G,H,X, p) by mapping the dart
(g, gx) to the dart (kg, kgx) in GCM(G,H,X, p−1), for any fixed k ∈ G \ H and all
g ∈ G and x ∈ X , is a map isomorphism between the maps GCM(G,H,X, p) and
GCM(G,H,X, p−1). This relatively simple task is left to the reader.
To obtain examples of orientable generalized Cayley maps that are not Cayley maps,
one needs to consider embeddings of Cayley graphs of even order. To obtain an ‘easy’
example, one could consider the generalized Cayley mapGCM(G,H,X, p) for the groups
G = Z2n, n ≥ 1, H = ⟨2⟩, X = G \ {0}, and any cyclic permutation p of X . All of these
maps are embeddings of the complete graphs K2n in orientable surfaces. However, it is
easy to see that the cases n = 1 and n = 2 result in Cayley maps, and even for n ≥ 3, it is
hard to show that the resulting maps are not Cayley. Thus, to construct an infinite family of
orientable generalized Cayley maps which are provably not Cayley maps, one might rely
on the Petrie dual operator again. Specifically, in what follows, we shall consider orientable
generalized Cayley maps whose Petrie dual is orientable again. Because of Theorem 4.2,
each such map must be bipartite (which is also a sufficient condition). Thus, we obtain the
following:
Theorem 5.2. Let M be an orientable generalized Cayley map. The Petrie dual of M is
orientable if and only if M = CM(G,X, p) is a Cayley map for a group G that contains
10 Ars Math. Contemp. 24 (2024) #P3.01
a subgroup H of index 2 for which X ⊆ G \H or if M = GCM(G,H,X, p) where H is
a subgroup of G of index 2 for which X ⊆ G \H .
Furthermore, if the Petrie dual of an orientable generalized Cayley map M is ori-
entable, the two maps CM(G,X, p) and GCM(G,H,X, p) are mutual Petrie duals.
Proof. In order for a Cayley graph C(G,X) to be bipartite, it is easy to see (and well
known) that it must be a Cayley graph of an even order group G that possesses a subgroup
H of index 2, and X must be a subset of the non-trivial coset of H in G. The rest of the
first part of the theorem follows from Theorem 5.1.
Suppose now that M = CM(G,X, p) with X satisfying the required condition with
respect to a subgroup H of G. It is again not too hard to see that the Petrie dual to M
reverses the order of elements fromX for each element ofH (or for each element ofG\H;
the two maps GCM(G,H,X, p) and GCM(G,H,X, p−1) are isomorphic as argued in
Theorem 5.1).
Clearly, an orientable generalized Cayley map M = GCM(G,H,X, p) is not simulta-
neously a Cayley map if and only if the group Aut(M) contains no orientation preserving
subgroup acting regularly on the vertices of M. One way to make sure no such group
exists, is to find a pair of vertices u, v of M for which there is no orientation preserving
automorphism mapping u to v. This is the approach we take to construct an infinite family
of orientable generalized Cayley maps which are not Cayley maps.
Lemma 5.3. Let G be a finite group with a subgroup H of index 2 and a generating set
X ⊆ G \H . If CM(G,X, p) is chiral, its Petrie dual GCM(G,H,X, p) is a generalized
Cayley map that is not a Cayley map.
Proof. Recall that an orientably regular map is chiral if it admits no orientation reversing
automorphisms. Note also, that since CM(G,X, p) is bipartite and connected, any auto-
morphism φ ∈ AutCM(G,X, p) that maps a vertex u ∈ H to a vertex v ∈ G \H maps
all elements of H onto the elements of G \ H . This means that all the automorphisms
in AutGCM(G,H,X, p) mapping elements of H to elements in G \ H are orientation
reversing, and no orientation preserving automorphisms of GCM(G,H,X, p) map the el-
ements of H to the elements in G \H . It follows that GCM(G,H,X, p) is not a Cayley
map.
Remark 5.4. There are many examples of chiral bipartite Cayley maps. One good source
of such maps is the paper [10] the authors of which construct infinitely many orientably
regular embeddings of Kn,n, with n = pe where p is an odd prime and e ≥ 1, which are
Cayley maps for cyclic and dihedral groups and are chiral. Lemma 5.3 yields that all their
Petrie duals are generalized Cayley maps that are not Cayley maps. A simpler family of
chiral bipartite Cayley maps, brought to our attention by one of our referees, is also formed
by the torus maps {4, 4}b,c, for b, c both non-zero, b + c even, and b ̸= c to guarantee
chirality, and the torus maps {6, 3}b,c. The chiral bipartite {4, 4}b,c maps have orders b2 +
c2 and arise by identifying opposite sides of squares with corners (0, 0), (b, c), (b−c, b+c)
and (−c, b) in a unit rectangular grid.
Example 5.5. Consider the dihedral groups
Dn =
〈
a, b | an = b2 = 1, bab−1 = a−1
〉
,
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 11
n ≥ 3. Taking G = Dn, H = ⟨a⟩ and X = {b, ba, . . . , ban−1} yields a pair of mutu-
ally Petrie dual generalized Cayley maps CM(G,X, p) and GCM(G,H,X, p), for every
cyclic permutation p of X . All such maps are orientable embeddings of the complete bi-
partite graph Kn,n. Taking the specific permutation p = (b, ba, . . . , ban−1) yields two
(possibly isomorphic) embeddings of Kn,n. First, the Cayley map
CM(Dn, {b, ba, . . . , ban−1}, (b, ba, . . . , ban−1))
is an orientable embedding of Kn,n with n faces of length 2n and of genus
(n−1)(n−2)
2 ,
while its Petrie dual
GCM(Dn, ⟨a⟩ , {b, ba, . . . , ban−1}, (b, ba, . . . , ban−1))
is an orientable embedding of Kn,n with the same number of faces of the same length and
of the same genus.
The excluded case n = 2 results in an embedding of K2,2 in the sphere of the form
CM(Z22, {(0, 1), (1, 1)}, ((0, 1), (1, 1)))
which is its own Petrie dual because the inverse of the permutation ((0, 1), (1, 1)) is
((0, 1), (1, 1)) again.
The toroidal maps for case n = 3 are pictured below.
b
a2
ba2 a
ba
1
b
a
ba2 a2
ba
1
Figure 1: Maps CM(D3, {b, ba, ba2}, (b, ba, ba2)) and GCM(D3, ⟨a⟩ , {b, ba, ba2},
(b, ba, ba2)).
Clearly, the two maps pictured in Figure 1 are isomorphic. Hence, the smallest maps
CM(D3, {b, ba, ba2}, (b, ba, ba2)) and CM(Z22, {(0, 1), (1, 1)}, ((0, 1), (1, 1)))) are self-
Petrie-dual. This might come as a surprise, as the same permutations of vertices (com-
ing from left multiplications) cannot simultaneously extend into orientation preserving
and orientation reversing automorphisms. It is, however, easy to notice that relabeling
the vertices of CM(D3, {b, ba, ba2}, (b, ba, ba2)) changes the permutation actions of left-
multiplications, and hence left multiplications with respect to one labeling may extend to
orientation preserving while left multiplications with respect to another labeling may ex-
tend to orientation reversing automorphisms. Since in non-bipartite cases the Petrie dual of
an orientable map is non-orientable, the case of bipartite orientable maps is the only case
where one may encounter orientable self-Petrie-dual generalized Cayley maps.
12 Ars Math. Contemp. 24 (2024) #P3.01
We devote the rest of this section to the investigation of such possibility, i.e., to the study
of orientable self-Petrie-dual generalized Cayley maps. Namely, suppose an orientable
generalized Cayley map M is self-Petrie-dual. Then, M is bipartite and Theorem 5.1 im-
plies that the automorphism group of M contains two subgroups acting regularly on the
vertices, a subgroup of orientation preserving automorphisms as well as a subgroup of au-
tomorphisms half of which is orientation reversing. This yields a necessary condition for
M being self-Petrie-dual, namely, M must be a Cayley map admitting at least one orienta-
tion reversing automorphism. Thus, chiral bipartite Cayley maps are never self-Petrie-dual
(in Example 5.4, we have already encountered infinitely many such maps constructed in
[10]). In fact, it is well-known that no chiral maps are self-Petrie-dual.
These observations appear to suggest that in order to construct bipartite Cayley maps
that are self-Petrie-dual, one should consider maps with many orientation preserving and
many orientation reversing automorphisms. In fact, searching through the literature for
orientable self-Petrie-dual maps resulted only in regular orientable self-Petrie-dual maps
[2, 11, 17], with the methods used in [11] or [17] relying on regularity and producing large
maps of large genera. An infinite family of regular examples also arises as follows.
Remark 5.6. For every positive integer n ≥ 2 that is relatively prime to φ(n) (i.e., there
exists a unique group of order n), there exists exactly one orientably regular embedding
of Kn,n [9]. That means that such embedding is necessarily isomorphic to its mirror re-
flection, hence regular, as well as self-Petrie dual. Kwak and Kwon in [13] classified the
orientable regular self-Petrie embeddings of Kn,n.
Nevertheless, even in the extreme case when M is regular, it might happen that any
orientation preserving subgroup K ≤ Aut(M) of order half the number of vertices of
M paired with any orientation reversing automorphism ψ ∈ Aut(M) generate a group of
order larger than the number of vertices of M. In that case, Aut(M) does not contain a
subgroup of automorphisms containing an orientation reversing automorphism and acting
regularly on the vertices. Hence, M cannot be isomorphic to any GCM(G,H,X, p), and
hence cannot be self-Petrie-dual. To illustrate this possibility, in the following example we
present an infinite family of bipartite regular Cayley maps none of which are self-Petrie-
dual. We are thankful to Gareth Jones who pointed out this example to us.
Remark 5.7. The authors of [3] considered regular embeddings of Kn,n having the prop-
erty that the orientation preserving automorphism group of the embedding that does not
move the bipartite sets is not metacyclic; in which case n is necessarily a power of 2.
For each such n ≥ 8, they construct four non-isomorphic regular orientable embeddings
of Kn,n, denoted N (n; k, l), k, l ∈ {0, 1}. They prove that the maps N (n; 0, 0) and
N (n; 1, 0) are self-Petrie-dual, while N (n; 0, 1) and N (n; 1, 1) are Petrie duals of each
other. They also show that all four maps are Cayley maps. This means, in particular, that
each of the maps N (n; 0, 1) and N (n; 1, 1) is both a Cayley map and an orientable gener-
alized Cayley map, and as such, they both admit both an orientation preserving as well as
an orientation reversing automorphism group acting regularly on the vertices of the maps.
Hence, not even the existence of both types of vertex-regular groups is sufficient for
making a generalized Cayley map self-Petrie. It is hard to say whether these non-metacyclic
maps are in any way typical, and whether a regular bipartite Cayley map is more likely to
be self-Petrie-dual or not. The following highly specialized result appears to be of some
relevance toward answering this question:
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 13
Theorem 5.8 ([17]). There are no regular, self-dual, self-Petrie-dual, normal Cayley maps
with odd vertex degree.
6 Non-orientable generalized Cayley maps and their Petrie duals
Even though constructing non-orientable generalized Cayley maps is relatively easy – it is
enough to consider the Petrie dual of any non-bipartite orientable generalized Cayley map
– a more explicit construction of such maps is needed. When considering only the Petrie
duals of orientable generalized Cayley maps, one would never encounter a non-orientable
generalized Cayley map whose Petrie dual is not orientable. To see that such maps might
exist, one just needs to realize that the Petrie dual of a non-orientable generalized Cayley
map whose underlying graph is bipartite (we will construct such maps) is necessarily non-
orientable. The present section differs from the previous section which was concerned with
maps whose groups are transitive on arcs (regular and orientably regular). In this section,
we abandon the focus on such highly symmetric generalized Cayley maps and seek only to
provide examples of various non-orientable generalized Cayley maps.
To specify an embedding of a graph in a non-orientable surface, one needs to spec-
ify the local orientation of outgoing darts around every vertex as well as to specify for
each edge whether the two local orientations associated with its end-vertices are consistent
or not. More precisely, for any given edge e incident with vertices u and v, let U be an
open neighborhood of e which includes both u and v and all of e, but no other vertices
and no other complete edges. Then U is homeomorphic to an open disk, and is therefore
an orientable topological object. By calling the two local orientations associated with the
end-vertices of e consistent, we mean that the local orientations around u and v within U
are both clockwise or both anti-clockwise. We call them inconsistent otherwise. Refer-
ring to the ribbon graph associated with the map, the edges with inconsistent end-vertex
orientations are sometimes also called twisted, as the strip containing the edge e and the
vertices u and v is twisted before being attached to the rest of the ribbon graph through the
vertices u and v. To indicate whether the end-vertex orientations of an edge are consistent
or not, one usually assigns 1 or −1 to the edge, respectively (or, in a visualization of the
graph embedding using local rotations, an edge with inconsistent end-vertex orientations is
marked by an ‘x’). Perhaps the biggest disadvantage of this description of an embedding of
a graph is the fact that one does not have a guarantee that the resulting embedding is indeed
non-orientable. For example, the bipartite orientable maps GCM(G,H,X, p) defined in
the previous section can also be described using this ‘non-orientable’ description by saying
that GCM(G,H,X, p) is the map in which the local rotation at each vertex is equal to p
and all edges have inconsistent end-vertex orientations.
As explained in the previous sections, a generalized Cayley map must be an embedding
of a Cayley graph C(G,X) with the property that each left multiplication by the elements
of G extends into a map automorphism of the embedding. One of the finer points to be
dealt with in the previous section was the fact that the extensions might be either orientation
preserving or orientation reversing. We do not have two kinds of map automorphisms in
non-orientable maps which makes the situation a bit easier.
Let us start by describing general embeddings of Cayley graphs. Let C(G,X) be a
Cayley graph, let ρg denote the local rotation of the elements of X around g, and let
ι{g,gx} ∈ {1,−1} be the label assigned to the edge {g, gx}. The three defining involu-
14 Ars Math. Contemp. 24 (2024) #P3.01
tions r0, r1, r2 are then defined as follows:
(g, c{g,gx}, cF )
r0 =
{
(gx, c{g,gx}, cF ), if ι{g,gx} = 1,
(gx, c{g,gx}, cF ′), if ι{g,gx} = −1
,
(g, c{g,gx}, cF )
r1 = (g, c{g,gρι{g,gx}g (x)}
, cF ), and (g, c{g,gx}, cF )r2 = (g, c{g,gx}, cF ′),
where F ′ is the face adjacent to F across the edge {g, gx}.
The following characterization of generalized Cayley maps can be already found in
both [19] and [12]. As stated above, it covers both the orientable and the non-orientable
generalized Cayley maps.
Theorem 6.1 ([12, 19]). A (orientable or non-orientable) map M is a generalized Cayley
map if and only if it is an embedding of a Cayley graph C(G,X) with all local cyclic per-
mutations ρg , g ∈ G, equal to a fixed cyclic permutation p of X , and the twist distribution
ι satisfying the property ι{g,gx} = ι{g′,g′x}, for all g, g′ ∈ G and x ∈ X .
The simplest interpretation of the last condition is that all edges labelled by the same
generator (or its inverse) must be either all simultaneously un-twisted or all twisted, and
hence, from now on, we will assume that ι acts on the set X , ι : X → {−1, 1}, mapping
x ∈ X to ι{g,gx} (thus, in particular, ι(x) = ι(x−1)), for all x ∈ X . As each generalized
Cayley map is determined by the four-tuple (G,X, p, ι), we will denote these maps by
GCM(G,X, p, ι).
The authors of [12] generalized this simplification even further and introduced the fol-
lowing convenient notation.
Let M = GCM(G,X, p, ι) be a generalized Cayley map. Without loss of generality,
we may assume that X = {x0, x1, . . . , xd−1}, while p(xi) = xi+1, for all i ∈ [d] =
{0, 1, 2, . . . d−1} (with the addition performed modulo d). If we denote the distribution of
inverses in X by the function κ : [d] → [d], satisfying the property (xi)−1 = xκ(i), and use
the fact that ι assigns the same value to all edges arising from right mutiplication by xi to
define (with just a hint of abuse of the notation) ι : [d] → {−1, 1}, ι(i) = ι{1g,xi} (note that
ι(κ(i)) = ι(i), for all i ∈ [d]), we may associate the flags of M with the ordered triples
from G × [d] × {−1, 1}, with the neighboring flags (g, c(g,gxi), cF ) and (g, c(g,gxi), cF ′)
corresponding to the triples (g, i, 1) and (g, i,−1). The defining involutions take then the
particularly simple form:
(g, i, j)r0 = (gxi, κ(i), ι(i)j), (g, i, j)
r1 = (g, i+ j, j), and (g, i, j)r2 = (g, i,−j).
Remark 6.2. It is now easy to construct infinitely many non-orientable generalized Cayley
maps. As is well-known (see e.g., [4]), an embedding of a graph determined by local ro-
tations and a twisting function is non-orientable if and only if it contains at least one cycle
with an odd number of twisted edges. Hence, for example, it is easy to construct infinitely
many non-orientable embeddings of the complete bipartite graphs Kn,n. To get such an
embedding, one can take a bipartite C(G,X) with G containing a subgroup H of index 2,
X = G \H = {x0, x1, . . . , x|G|/2−1}, satisfying the only additional condition that x20 ̸=
x−12 x
−1
1 , choose any cyclic permutation p of X , twist the edges labeled by x0, and observe
that the 4-cycle consisting of the vertices 1G, x0, x0x1, x0x1x2, x0x1x2(x0x1x2)−1 = 1G
obtained by successive multiplications by x0, x1, x2 and (x0x1x2)−1 (which, being an odd
product of elements from X , necessarily belongs to X) contains the twisted edge labeled
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 15
x0 exactly once (if (x0x1x2)−1 were equal to x0, we would get the identity x−12 x
−1
1 = x
2
0
which we explicitely prohibited). Hence, all such generalized Cayley maps GCM(G,X,
p, ι) are unorientable embeddings of complete bipartite graphs, and there are clearly in-
finitely many of them. Note also that all such maps, being embeddings of bipartite graphs,
have the property that their Petrie dual is non-orientable.
Next, we bring in the Petrie dual operator again and fully describe its action on gener-
alized Cayley maps. The mapping −ι used in the statement of the following theorem is the
twisting function −ι(x) = (−1) · ι(x), for all x ∈ X .
Theorem 6.3. If M = GCM(G,X, p, ι), then P (M) = GCM(G,X, p,−ι).
Proof. It is easy to see that −ι is a correctly defined twisting function of a generalized Cay-
ley map, i.e., −ι(x) = −ι(x−1), for all x ∈ X . Since the two maps GCM(G,X, p,−ι)
and P (GCM(G,X, p, ι)) have the same underlying graphs, one way to prove our the-
orem is to show that the Petrie polygons of GCM(G,X, p, ι) and the faces of the map
GCM(G,X, p,−ι) are identical. This can be shown by performing a careful calculation
of the boundaries of the two oriented Petrie polygons of GCM(G,X, p, ι) that start at
(g, i) (which might turn out to be the same polygon visiting (g, i) twice, once followed
along p and once followed along p−1, depending on whether we first turn ‘right’ or ‘left’)
and the boundaries of the corresponding faces in GCM(G,X, p,−ι). As pointed out by
one of our referees, it can also be deduced from the fact that if r0, r1, r2 are the generators
of the monodromy group of GCM(G,X, p, ι), then r0r2, r1, and r2 are the generators for
the monodromy group of P (GCM(G,X, p, ι)) (Section 4) while they can also be easily
seen to be the generators of the monodromy group of GCM(G,X, p,−ι).
Based on the above theorem, obtaining the Petrie dual for a Cayley map is very simple.
Namely, the Petrie dual of a Cayley map CM(G,X, p) is the generalized Cayley map
GCM(G,X, p, ι), where ι twists all the edges of the map, i.e., ι(x) = −1, for every
x ∈ X . Since all the edges are twisted, the Petrie dual of a Cayley map M is non-
orientable if and only if M contains at least one odd cycle (i.e., the underlying graph is
non-bipartite). Hence, Theorem 5.2 is a corollary of Theorem 6.3.
Example 6.4. To obtain a specific example of the use of Theorem 6.3, we go back to a
classical example of a pair of mutually Petrie dual maps, namely the regular embedding of
the tetrahedron on the sphere and its Petrie dual embedded in the projective plane. Since
tetrahedron is the Cayley map CM(Z2 × Z2, {(1, 0), (0, 1), (1, 1)}, ((1, 0), (0, 1), (1, 1)))
with 4 triangular faces, its Petrie dual is the generalized Cayley map
GCM(Z2 × Z2, {(1, 0), (0, 1), (1, 1)}, ((1, 0), (0, 1), (1, 1)), ι),
with ι(x) = −1 for all x ∈ {(1, 0), (0, 1), (1, 1)}. Since the tetrahedron contains odd
cycles (triangles), the dual map is non-orientable, well-known to be an embedding in the
projective plane with 3 faces of length 4 (which can also be easily verified via direct calcu-
lations in the generalized Cayley map).
This example can be viewed as the first member of an infinite family of examples. For
every even n ≥ 4, let Dn = ⟨a, b | an = b2 = 1, bab = a−1⟩ be the dihedral group of
order 2n, X = {b, an2 , ba} be a set of three involutions, and p = (b, an2 , ba). Since n is
assumed even, the Petrie dual of the trivalent Cayley map CM(Dn, X, p) is non-orientable
(as the underlying graph of both maps contains a cycle of lenght n + 1). For even n ≥ 4,
16 Ars Math. Contemp. 24 (2024) #P3.01
the Petrie dual of CM(G,X, p) looks ‘like’ the Petrie dual of the tetrahedron: a 2n-cycle
with inside chords at every other vertex of the cycle, and an outside edge for the rest. All
these Petrie duals are embeddings in the projective plane with one face of length 2n and all
the remaining faces of length 4.
1 ba
b
a
a3
ba2
a2
ba3
Figure 2: Representation of the Petrie dual of the map CM(D4, {b, a2, ba}, (b, a2, ba))
indicating local rotations and marking the edges with inconsistent end-vertex rotations of
its underlying graph.
Next, we characterize non-orientable generalized Cayley maps whose Petrie dual is
orientable. As should be expected, those are the ‘obvious’ Petrie duals of non-bipartite
orientable Cayley maps, i.e., the non-bipartite non-orientable generalized Cayley maps sat-
isfying ι(x) = −1, for all x ∈ X , as well as other maps with a rather special twisting
function. The Petrie duals of all other non-orientable generalized Cayley maps are non-
orientable.
Corollary 6.5. The Petrie dual of a non-orientable generalized Cayley map GCM(G,X,
p, ι) is orientable if and only if the underlying Cayley graph C(G,X) contains an odd
cycle and every cycle of C(G,X) contains an even number of untwisted edges.
Proof. Suppose that M = GCM(G,X, p, ι) is non-orientable while its Petrie dual
P (M) = GCM(G,X, p,−ι) is orientable. This means that M cannot be bipartite as
that would make the orientable P (M) bipartite and hence by Theorem 5.2 its Petrie dual
P (P (M)) = M orientable; which it is not. Thus M contains an odd cycle. If any cycle in
M contained an odd number of untwisted edges, that very same cycle would contain an odd
number of twisted edges in P (M); making it non-orientable. This proves one implication.
Suppose now that M is non-orientable, contains an odd length cycle and every cycle
of M contains an even number of untwisted edges. Then M is not bipartite and its Petrie
dual contains no cycles with an odd number of twisted edges.
As stated prior to Theorem 6.3, non-orientable non-bipartite generalized Cayley maps
with all edges twisted trivially satisfy the property that their Petrie dual is also non-
orientable. Next, we provide an infinite family of examples that satisfy the conditions
of Theorem 6.3 but contain both twisted and untwisted edges.
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 17
Example 6.6. Let Γ be a bipartite d-regular graph, d-odd, let M be any orientable em-
bedding of Γ, and ρ and λ be the generators for the monodromy group G of M. Con-
sider the Cayley graph C(G, {ρ, ρ−1, λ}). There is an easy way to visualize this graph.
It is the underlying graph of the truncation T (M) of M, i.e., the map obtained from
M by locally removing its vertices and replacing them by d-cycles attached to the dan-
gling edges in the order determined by the local rotation. We claim that every cycle of
C(G, {ρ, ρ−1, λ}) contains an even number of edges labeled λ. To see this, take any cycle
C of C(G, {ρ, ρ−1, λ}). The edges labeled λ trace the ‘preimage’ of this cycle in Γ, which
is necessarily a union of edge disjoint even cycles. Since every edge labeled λ in C corre-
sponds to exactly one edge of the preimage, the number of edges labeled λ in C is even.
Thus, any choice of p together with the twisting function ι(ρ) = ι(ρ−1) = −1, ι(λ) = 1
makes the non-orientable GCM(G,X, p, ι) satisfy the conditions of Theorem 6.3.
The visualization of this example is in fact quite simple. We start with a ‘bipartite’
map whose ‘vertices’ are the d-cycles formed by edges labelled ρ, all of which are twisted,
with the edges labelled λ and connecting the two sets of d-cycles untwisted. This map is
non-orientable, since d is required to be odd. The orientable dual untwists the d-cycles and
twists the connecting edges.
To conclude this section, we consider one more classical concept from topological
graph theory – the orientable double covering Mo of a non-orientable map M given by its
underlying graph, rotation system and twisting function. The underlying graph of the dou-
ble covering is the Z2-lift of the underlying graph of the original map with the untwisted
edges given the voltage 0 ∈ Z2, and the twisted edges receiving the voltage 1 ∈ Z2. Infor-
mally, it is the double cover of the underlying graph of the original map with the untwisted
edges each lifted into two edges connecting vertices in the same layer, and the two lifts of
the twisted edges crossing from one layer to the other (for more details consult [20]). The-
orem 2.4 in [20] asserts that Aut(M) lifts into the orientation preserving automorphism
group Aut+Mo, and the full group Aut(M)o is the direct product of Aut+Mo with some
orientation reversing involutory automorphism ψ of order 2 (that swaps the two layers of
the double covering). It follows that the direct product of the lift of a subgroup of Aut(M)
acting regularly on the vertices of M with the group ⟨ψ⟩ acts regularly on the vertices of
Mo, and we obtain:
Theorem 6.7. The orientable double covering Mo of any non-orientable generalized Cay-
ley map M is an orientable generalized Cayley map admitting a group of automorphisms
containing an orientation reversing automorphism and acting regularly on its vertices.
7 Regular generalized Cayley maps
In conclusion of our paper, we would like to direct the reader toward [12] where the authors
of that paper developed a complete theory of regular generalized Cayley maps including
necessary and sufficient conditions based on the existence of special permutations of the
elements of the underlying group. Their language, however, is different from the one used
here, and they do not consider the orientable generalized Cayley maps GCM(G,H,X, p)
as a special case.
ORCID iDs
Robert Jajcay https://orcid.org/0000-0002-2166-2092
18 Ars Math. Contemp. 24 (2024) #P3.01
Jozef Širáň https://orcid.org/0000-0002-5901-7646
Yan Wang https://orcid.org/0000-0002-0148-2932
References
[1] M. Abas, personal communication.
[2] G. Cunningham, Self-dual, self-Petrie covers of regular polyhedra, Symmetry 4 (2012), 208–
218, doi:10.3390/sym4010208, https://doi.org/10.3390/sym4010208.
[3] S.-F. Du, G. Jones, J. H. Kwak, R. Nedela and M. Skoviera, Regular embeddings of Kn,n
where n is a power of 2. II: the non-metacyclic case, Eur. J. Comb. 31 (2010), 1946–1956,
doi:10.1016/j.ejc.2010.01.009, https://doi.org/10.1016/j.ejc.2010.01.009.
[4] J. L. Gross and T. W. Tucker, Topological Graph Theory, Dover Publications, Inc., Mineola,
NY, 2001, reprint of the 1987 original (Wiley, New York).
[5] R. Jajcay, Automorphism groups of Cayley maps, J. Comb. Theory Ser. B 59 (1993), 297–310,
doi:10.1006/jctb.1993.1071, https://doi.org/10.1006/jctb.1993.1071.
[6] R. Jajcay, C.-H. Li, J. Širáň and Y. Wang, Regular and orientably-regular maps with quasiprim-
itive automorphism groups on vertices, Geom. Dedicata 203 (2019), 389–418, doi:10.1007/
s10711-019-00440-6, https://doi.org/10.1007/s10711-019-00440-6.
[7] R. Jajcay and J. Širáň, Skew-morphisms of regular Cayley maps, Discrete Math. 244
(2002), 167–179, doi:10.1016/S0012-365X(01)00081-4, https://doi.org/10.1016/
S0012-365X(01)00081-4.
[8] L. D. James and G. A. Jones, Regular orientable imbeddings of complete graphs, J. Comb. The-
ory Ser. B 39 (1985), 353–367, doi:10.1016/0095-8956(85)90060-7, https://doi.org/
10.1016/0095-8956(85)90060-7.
[9] G. A. Jones, Regular embeddings of complete bipartite graphs: classification and enumeration,
Proc. Lond. Math. Soc. (3) 101 (2010), 427–453, doi:10.1112/plms/pdp061, https://doi.
org/10.1112/plms/pdp061.
[10] G. A. Jones, R. Nedela and M. Škoviera, Regular embeddings of Kn,n where n is an odd
prime power, Eur. J. Comb. 28 (2007), 1863–1875, doi:10.1016/j.ejc.2005.07.021, https:
//doi.org/10.1016/j.ejc.2005.07.021.
[11] G. A. Jones and M. Ziv-Av, Petrie duality and the Anstee-Robertson graph, Symmetry 7 (2015),
2206–2223, doi:10.3390/sym7042206, https://doi.org/10.3390/sym7042206.
[12] J. H. Kwak and Y. S. Kwon, Unoriented Cayley maps, Studia Sci. Math. Hungarica 43 (2006),
137–157, doi:10.1556/SScMath.43.2006.2.1, https://doi.org/10.1556/SScMath.
43.2006.2.1.
[13] J. H. Kwak and Y. S. Kwon, Classification of reflexible regular embeddings and self-Petrie dual
regular embeddings of complete bipartite graphs, Discrete Math. 308 (2008), 2156–2166, doi:
10.1016/j.disc.2007.04.062, https://doi.org/10.1016/j.disc.2007.04.062.
[14] C. H. Li and J. Širáň, Regular maps whose groups do not act faithfully on vertices, edges,
or faces, Eur. J. Comb. 26 (2005), 521–541, doi:10.1016/j.ejc.2003.09.022, https://doi.
org/10.1016/j.ejc.2003.09.022.
[15] R. Nedela and M. Škoviera, Maps, in: J. Gross, J. Yellen and P. Zhang (eds.), Handbook of
Graph Theory, 2nd ed., CRC Press, Boca Raton, FL, pp. 820–859, 2013, doi:10.1201/b16132,
https://doi.org/10.1201/b16132.
[16] R. B. Richter, J. Širáň, R. Jajcay, T. W. Tucker and M. E. Watkins, Cayley maps, J. Comb. The-
ory Ser. B 95 (2005), 189–245, doi:10.1016/j.jctb.2005.04.007, https://doi.org/10.
1016/j.jctb.2005.04.007.
R. Jajcay et al.: Generalized Cayley maps and their Petrie duals 19
[17] R. B. Richter, J. Širáň and Y. Wang, Self-dual and self-Petrie-dual regular maps, J. Graph
Theory 69 (2012), 152–159, doi:10.1002/jgt.20570, https://doi.org/10.1002/jgt.
20570.
[18] G. Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426–438, doi:10.1007/
BF01304186, https://doi.org/10.1007/BF01304186.
[19] T. W. Tucker, Symmetric embeddings of Cayley graphs in nonorientable surfaces, in: Graph
Theory, Combinatorics, and Applications. Vol. 2 (Kalamazoo, MI, 1988), Wiley, New York,
Wiley-Intersci. Publ., pp. 1105–1120, 1991.
[20] J. Širáň and T. W. Tucker, Symmetric maps, in: L. W. Beineke and R. J. Wilson (eds.), Topics
in Topological Graph Theory, Cambridge University Press, Cambridge, volume 128 of En-
cyclopedia Math. Appl., pp. 199–224, 2009, doi:10.1017/CBO9781139087223.013, https:
//doi.org/10.1017/CBO9781139087223.013.
[21] M. Škoviera and J. Širáň, Regular maps from Cayley graphs. I: Balanced Cayley maps, Dis-
crete Math. 109 (1992), 265–276, doi:10.1016/0012-365X(92)90296-R, https://doi.
org/10.1016/0012-365X(92)90296-R.
[22] S. E. Wilson, Operators over regular maps, Pacific J. Math. 81 (1979), 559–568, http://
projecteuclid.org/euclid.pjm/1102785296.