#  Orientably-regular embeddings of complete multigraphs

###### Abstract

An embedding of a graph on an orientable surface is orientably-regular (or
rotary, in an equivalent terminology) if the group of orientation-preserving
automorphisms of the embedding is transitive (and hence regular) on incident
vertex-edge pairs of the graph. A classification of orientably-regular
embeddings of complete graphs was obtained by L. D. James and G. A. Jones [in
”Regular orientable imbeddings of complete graphs”, J. Combinatorial Theory
Ser. B 39 (1985), 353–367], pointing out interesting connections to finite
fields and Frobenius groups. By a combination of graph-theoretic methods and
tools from combinatorial group theory we extend results of James and Jones to
classification of orientably-regular embeddings of complete multigraphs with
arbitrary edge-multiplicity.

Štefan Gyürki

Slovak University of Technology, Bratislava, Slovakia

Soňa Pavlíková

A. Dubček University, Trenčín, Slovakia

Jozef Širáň

Slovak University of Technology, Bratislava, Slovakia

##  1 Introduction

Cellular embeddings of connected graphs on compact orientable surfaces, or,
simply, maps, provide important links between discrete mathematics, low-
dimensional topology and Riemann surfaces, extending to group theory and
Galois theory if the maps are ‘highly symmetric’. To be more specific about
the latter, an automorphism of a map is an automorphism of its underlying
graph that preserves the cell structure of a map and orientation of its
carrier surface; a map is orientably-regular if the group of all its
automorphisms acts regularly on incident vertex-edge pairs of its underlying
graph. Orientable regularity is known to be a formal way of expressing the
‘highest level of symmetry’ a map can have with respect to orientation-
preserving automorphisms, cf. [13].

Classification of orientably-regular maps, both per se as well as because
applications to symmetric Riemann surfaces, turns out to be an important
challenge and has been pursued for more than a century. Since the concept of
an orientably-regular map encompasses an interplay of three kinds of objects
(graphs, surfaces, and groups), classification of such maps broadly follows
three directions, depending on the object of primary interest. Leaving aside a
number of deep results obtained in classification of orientably-regular maps
with a given automorphism group, or on a given surface, we confine ourselves
only to a brief survey on classification results for orientably-regular maps
with a given underlying graph, focusing on important infinite families of
graphs.

The four highlights in this area of research are classifications of
orientably-regular embeddings of complete graphs [11], complete bipartite
graphs [14], complete multipartite graphs with at least three parts [5], and
cubes of arbitrary finite dimension [1]. In all four cases the results are
highly non-trivial, despite targeting well-studied families of graphs. Indeed,
one may naively ask about possible difficulties in sorting out orientably-
regular embeddings of complete graphs in which everything should be
understood. The paper [11], which is historically first in classification of
orientably-regular maps with a given underlying graph, presents a surprising
answer which includes deep connections of the problem with finite fields and
Frobenius groups. By its main result, a complete graph on $r$ vertices admits
an orientably-regular embedding if and only if $r=p^{k}$ for some prime $p$,
in which case there are exactly $\varphi(r-1)/k$ pairwise non-isomorphic
orientably-regular embeddings (where $\varphi$ is Euler’s function).

For completeness, although a general characterisation of graphs underlying
orientably-regular maps in terms of existence of a suitable subgroup of the
automorphism group of the graph was given in [7], the four major results
mentioned above illustrate a long way from this abstract characterisation to
results for particular families of graphs.

The aim of this paper is to extend the classification of orientably-regular
embeddings of complete graphs $K_{r}$ to complete multigraphs $K_{r}^{(t)}$ of
order $r$ in which every pair of vertices is joined by $t$ parallel edges for
some $t\geq 1$; we also speak of a complete graph with edge-multiplicity $t$.
A classification of such embeddings in the range $2\leq r\leq 5$ for every
$t\geq 1$ was obtained in [6] as part of a project to determine all
orientably-regular maps of order at most $5$; the cases $r=2$ and $r=3$ were
later revisited in [16] and [9] in different contexts. But beyond the above
range of $r$, classification remained completely open. In this place we offer
the following very brief excerpt from our main findings.

###### Theorem 1

A complete multigraph $K_{r}^{(t)}$ with $r\geq 5$ and edge-multiplicity
$t\geq 1$ admits an orientably-regular embedding if and only if $r$ is a prime
power, with $t$ odd if $r$ is odd. Moreover, if $r=p^{k}$ for some prime $p$
and $k\geq 1$, the number of mutually non-isomorphic orientably-regular
embeddings of $K_{r}^{(t)}$ is $\varphi(r-1)/k$ for every odd $t$ and
arbitrary $r\geq 5$, and $2\varphi(r-1)/k$ for every even $t\geq 2$ and every
even $r\geq 8$.

Our proofs rely on a combination of graph-theoretic arguments and tools from
combinatorial group theory. We actually give two refined versions of the above
theorem: one in terms of central cyclic extensions of automorphism groups of
regular embeddings of simple complete graphs (that is, those with edge-
multiplicity $1$), and a more detailed one in terms of group presentations.
For the latter we construct a suitable associated Cayley graph and apply the
Reidemeister-Schreier procedure, which is based on converting closed walks in
the associated graph to relators in group presentations. The methods apply to
every $r\geq 3$, furnishing also an explanation (via Schur multiplier) of why
the value of $r=4$ is a remarkable exception, as it also follows from [6].

The outlined approach determines the structure of the paper. After a
presentation of basic facts on orientably-regular maps (section 2) we review
specifications of the theory to underlying multigraphs with arbitrary edge-
multiplicity (section 3). This has been kind of folklore but we are not aware
of a synthetic approach we offer here, linking such embeddings with a
combinatorial description of presentations of the corresponding automorphism
groups. In section 4 we refine the known classification of orientably-regular
embeddings of simple complete graphs of prime power order by deriving
presentations of their automorphism groups, which we then extend to
corresponding complete multigraphs of arbitrary edge-multiplicity for prime
powers larger than $4$ in section 5. The ‘singular values’ $2$, $3$ and $4$
are then handled separately in section 6, and we wrap up in section 7 by a
discussion of chirality, self-complementarity, Wilson operators, and Cayley
structure of the maps.

One may also wonder why one should be interested in investigation of
orientably-regular embeddings of multigraphs at all. The perhaps best answer
is provided by an inspection of a computationally generated list of
presentations of automorphism groups of all orientably-regular maps on
surfaces up to genus $300$ [2], in which only $11$ per cent are such that both
the map and its dual have a simple underlying graph. It appears that, at least
for genera up to $300$, orientably-regular maps with multiple edges are vastly
predominant.

##  2 Orientably-regular maps: a brief review of theory

Let us begin by recalling that in the theory of maps, automorphisms of graphs
and maps are usually viewed as permutations of incident vertex-edge pairs,
commonly known as arcs. An automorphism of a map is thus a permutation of the
set of arcs of its underlying graph which is both an automorphism of the graph
and also preserves face boundary walks of the map, including their
orientations inherited from an orientation of the carrier surface of the map.
The group of all such automorphisms of a map ${\cal M}$ will be denoted ${\rm
Aut}^{+}{\cal M}$, the ‘plus’ superscript indicating that the group comprises
only orientation-preserving automorphisms; we will address their orientation-
reversing counterparts in section 7.

It is an elementary fact in the theory of maps that, for a map ${\cal M}$ as
above, the group ${\rm Aut}^{+}{\cal M}$ acts freely on the set of arcs of the
underlying graph of ${\cal M}$. In the case the action is also transitive, and
hence regular, we say that ${\cal M}$ is an orientably-regular map.
Equivalently, in an orientably-regular map ${\cal M}$, for each ordered pair
of arcs there exists an automorphism in ${\rm Aut}^{+}{\cal M}$ sending the
first arc of the pair onto the second.

Let now ${\cal M}$ be an orientably-regular map, formed by a cellular
embedding of its underlying graph $\Gamma$ on a compact orientable surface
${\cal S}$, oriented anti-clockwise, and let $a$ be an arbitrary but fixed arc
of $\Gamma$. By orientable regularity, there is an automorphism in ${\rm
Aut}^{+}{\cal M}$, which we denote $y$, mapping the arc $a$ to the
counterclockwise next arc $a^{\prime}$ of ${\cal M}$ incident to the same
vertex as $a$. Similarly, orientable regularity implies existence of another
automorphism in ${\rm Aut}^{+}{\cal M}$, denoted $x$ in what follows, which
sends the arc $a$ onto the anti-clockwise next arc on the face of ${\cal M}$
containing both $a$ and $a^{\prime}$. It may be checked that $a(xy)^{2}=a$,
and invoking orientable regularity again this means that $(xy)^{2}=1$ in ${\rm
Aut}^{+}{\cal M}$. Because of the facts that the automorphisms $x$, $y$ and
$xy$ act on ${\cal M}$ as local rotations around centre of a face, a vertex,
and centre of an edge (respectively), in an alternative terminology such maps
are also known as rotary [22].

Continuing with our orientably-regular map ${\cal M}$, connectedness of
$\Gamma$ (and hence of the carrier surface of the map) implies that the entire
group ${\rm Aut}^{+}{\cal M}$ is generated by the two permutations $x$ and
$y$. Further, and again by orientable regularity of the map, all its faces
must be bounded by boundary walks of the same length, say, $m$, and all its
vertices must have the same valency, say, $n$; using the traditional Schläfli
symbol the map is then said to be of type $\\{m,n\\}$. The connection of the
type to the generators $x$ and $y$ of ${\rm Aut}^{+}{\cal M}$ is simply that
entries of the type are orders of the generators, that is, $m={\rm ord}(x)$
and $n={\rm ord}(y)$. The group ${\rm Aut}^{+}{\cal M}$ thus admits a
presentation of the form $\langle x,y\ |\
x^{m},\,y^{n},\,(xy)^{2},\,\ldots\rangle$. This fact has a number of
consequences, out of which we outline only two in what follows.

First, as any structure preserved by a group acting regularly on building
blocks of the structure, the map ${\cal M}$ is completely determined by the
group $G={\rm Aut}^{+}{\cal M}=\langle x,y\rangle$ by identifying arcs with
elements of $G$ and faces, vertices and edges of the map with left cosets of
the subgroups $\langle x\rangle$, $\langle y\rangle$ and $\langle xy\rangle$,
respectively, with incidence defined by containments of elements in cosets and
non-empty intersection of cosets, and with automorphisms acting by right
multiplication. This way, orientably-regular maps of type $\\{m,n\\}$ may be
identified with finite groups generated by two elements, of order $m$ and $n$,
with product of order $2$.

Second, bearing in mind such an identification, a group $G$ given by a
presentation $\langle x,y\ |\ x^{m},\,y^{n},\,(xy)^{2},\,\ldots\rangle$ is a
smooth quotient of the well-known ordinary $(m,n,2)$-triangle group
$\Delta^{+}(m,n,2)=\langle X,Y\ |\ X^{m},\,Y^{n},\,(XY)^{2}\rangle$. The
latter is the group of orientation-preserving automorphisms of a universal
tessellation $U(m,n)$ of a simply-connected surface by $m$-gons, $n$ meeting
at each vertex; the surface is a sphere, a Euclidean plane or a hyperbolic
plane, depending on whether $1/m+1/n-1/2$ is positive, zero, or negative. The
smooth epimorphism $\Delta^{+}(m,n,2)\to G$ given by $X\mapsto x$ and
$Y\mapsto y$ translates to a smooth covering of the orientably-regular map
${\cal M}$ determined by $G$ by the tessellation $U(m,n)$, which can be used
to ‘pull down’ the complex structure from a simply-connected surface carrying
$U(m,n)$ onto the carrier surface of ${\cal M}$, making it a Riemann surface.

For further facts related to the theory of orientably-regular maps and their
relations to two-generated groups, Riemann surfaces and Galois theory we refer
to the seminal paper [13] laying foundations of the theory of maps on
orientable surfaces, and to a more recent survey [19]. The latter also
addresses regular maps, which, on orientable surfaces, arise if an orientably-
regular map admits also orientation-reversing automorphisms (and the concept
extends also to non-orientable surfaces); these will be briefly mentioned in
section 7.

##  3 Orientably-regular maps with multiple edges

As alluded to in the introduction, in this section we collect known facts on
relations between orientably-regular maps with a simple underlying graph and
orientably-regular embeddings of the corresponding multigraph, obtained by
‘inflating’ adjacencies in the original graph to any multiplicity $t\geq 1$.
We reiterate that most of the material has been known, but we are not aware of
a synthesis combining ideas from graph covers and combinatorial group theory
to derive a presentation of the automorphism group of the ‘inflated’ map terms
of the automorphism group of the original map.

Let $\cal M$ be an orientably-regular map of type $\\{m,n\\}$, with its group
$G={\rm Aut}^{+}{\cal M}=\langle x,y\ |\ x^{m},y^{n},(xy)^{2},\ldots\rangle$
of all orientation-preserving automorphisms. Assume that the underlying graph
$\Gamma$ of this map contains a pair of distinct vertices joined by exactly
$t$ parallel edges for some $t\geq 2$. Since $G$ acts on the graph arc-
transitively, every pair of adjacent vertices in $\Gamma$ is joined by $t$
parallel edges. Thus, $\Gamma$ has edge-multiplicity $t$ and valency $n=dt$
for some integer $d$, so that every vertex in $\Gamma$ has $d=n/t$ neighbours.
Assuming that $y$ is an $n$-fold rotation of $\cal M$ about a chosen vertex of
$\Gamma$, the subgroup $\langle y\rangle<G$ of order $n$ acts cyclically on
the $d$ neighbours of that vertex.

It follows that $y^{d}$ fixes not only the chosen vertex but also all its
neighbours, and as ${\cal M}$ is orientably-regular, $y^{d}$ fixes every
vertex of the map and so $N=\langle y^{d}\rangle$ is a normal subgroup of $G$.
The orientably-regular quotient map ${\cal M}/N$ then has a simple underlying
graph, namely, the quotient $\Gamma/N$, of valency $d=n/t$. The natural
projection ${\cal M}\to{\cal M}/N$ induces a branched covering of the two
maps, with branching index $t$ at every vertex.

One can turn around this line of thought and begin with an orientably-regular
map determined by a group $G=\langle x,y\rangle$ as above and assume that
$N=\langle y^{d}\rangle$ is a normal subgroup of $G$ for some divisor $d$ of
$n$. The subgroup $N$ again fixes every vertex of $\cal M$, and the quotient
map ${\cal M}/N$ will be orientably-regular, with the same number of vertices
as $\cal M$, and of valency $d$. The underlying graph of this map is simple if
and only if $N$ is the largest subgroup of $\langle y\rangle$ normal in $G$,
that is, if and only if $N$ is the core of $\langle y\rangle$ in $G$.

Returning to our original setting with $n=dt$ and edge-multiplicity $t$, note
that conjugation of $y^{d}$ by both $x$ and $xy$ results in the same power of
$y^{d}$, say, $y^{df}$, which gives rise to a relator of the form
$R=x^{-1}y^{d}xy^{-df}$ in the presentation of $G$. But because $xy$ is an
involution, it follows that $f^{2}\equiv 1$ mod $t$, with a consequence that
$[x^{2},y^{d}]=1$. Moreover, if $\Gamma$ (and, equivalently, $\Gamma/N$) is
not bipartite, then $f\equiv 1$ mod $t$. Indeed, $\Gamma$ then contains a
cycle of odd length $j$, which corresponds to a relator $W$ in $G$ of the form
$W=y^{\ell_{1}}xy^{\ell_{2}}x\ldots y^{\ell_{j}}x$. Applying $R$ in the
equivalent form $y^{d}x=xy^{df}$ successively $j$ times to the product
$y^{d}W$ to ‘move the term $y^{d}$ across $W$ from the left to the right’
results in $y^{d}W=Wy^{df^{j}}$, and since $W=1$ and $j$ is odd, it follows
that $f\equiv 1$ mod $t$. In particular, if $\Gamma$ is not bipartite, then
the relator $R$ reduces to the commutator $[x,y^{d}]=x^{-1}y^{-d}xy^{d}$.

Letting $H=G/N$ and $u=xN$, $v=yN$, the group $H\cong{\rm Aut}^{+}{\cal
M}^{\prime}$ of the quotient map ${\cal M}^{\prime}={\cal M}/N$ is generated
by $u$ and $v$ and admits a presentation of the form

$H=\langle u,v\ |\ u^{\ell},v^{d},(uv)^{2},{\rm Rels}\rangle$ (1)

for some divisor $\ell$ of $m$ and a finite collection $\rm Rels$ of relators
as words in $u$ and $v$.

We will now be interested in the reverse direction. Namely, assume that ${\cal
M}^{\prime}$ is an orientably-regular map of type $\\{\ell,d\\}$ with a simple
underlying graph, given by means of a presentation of its group $H={\rm
Aut}^{+}{\cal M}^{\prime}$ as in (1). For any given integer $t\geq 2$, we
would like to describe all orientably-regular maps ${\cal M}$ of type
$\\{m,n\\}$ for $n=dt$ (where $m$ is some multiple of $\ell$) such that the
underlying graph of ${\cal M}$ is obtained by replacing every edge of the
underlying graph of ${\cal M}^{\prime}$ by $t$ parallel edges. Each such
orientably-regular map ${\cal M}$ will be briefly called a $t$-inflation of
${\cal M}^{\prime}$, and in this terminology the task is to describe all
$t$-inflations of a given orientably-regular map with a simple underlying
graph.

The outlined theory implies that such a task reduces to describing suitable
normal extensions of $H$ by a cyclic group of order $t$; the procedure is well
known and we briefly describe its essence. Let $\langle u,v\ |\
u^{\ell},v^{d},(uv)^{2},{\rm Rels}\rangle$ be a presentation of $H={\rm
Aut}^{+}{\cal M}^{\prime}$ for an orientably-regular map ${\cal M}^{\prime}$
of type $\\{\ell,d\\}$ as in (1). Let ${\cal M}$ be a $t$-inflation of ${\cal
M}^{\prime}$, of type $\\{m,n\\}$ for $n=dt$ and $m$ a multiple of $\ell$,
with $G={\rm Aut}^{+}{\cal M}=\langle x,y\ |\
x^{m},y^{n},(xy)^{2},\ldots\rangle$. We saw that the two maps and the two
groups are related by ${\cal M}^{\prime}={\cal M}/N$ and $H=G/N$ for the
normal subgroup $N=\langle y^{d}\rangle$ of order $t$. Now, for every word
$w(u,v)$ in $\\{u^{\ell}\\}\cup\rm Rels$, let $w(x,y)$ be the corresponding
word in terms of $x$ and $y$ obtained from $w(u,v)$ by substituting $x$ and
$y$ for every occurrence of $u$ and $v$ in $w(u,v)$, respectively. Since
$w(x,y)N=w(xN,yN)=w(u,v)=1$, it follows that $w(x,y)\in N$, and so
$w(x,y)=(y^{d})^{e_{w}}$ for some integer $e_{w}$ depending on
$w=w(u,v)\in\\{u^{\ell}\\}\cup{\rm Rels}$.

By [12, Ch. 10, Proposition 1] adapted to maps setting, if an orientably-
regular map ${\cal M}$ is a $t$-inflation of an orientably-regular ${\cal
M}^{\prime}$ of type $\\{\ell,d\\}$ with $H={\rm Aut}{\cal M}^{\prime}$
presented as in (1), then the group $G={\rm Aut}^{+}{\cal M}$ admits a
presentation of the form

$G=\langle x,y\ |\ y^{n},(xy)^{2},x^{-1}y^{d}xy^{-df},\\{w(x,y)y^{-de_{w}};\
w=w(u,v)\in\\{u^{\ell}\\}\cup{\rm Rels}\\}\rangle$ (2)

for some integers $e_{w}$ for $w\in\\{u^{\ell}\\}\cup{\rm Rels}$ and $f$ such
that $f^{2}\equiv 1$ mod $t$, with $n=dt$.

Shifting focus to inflations of complete maps, let ${\cal M}$ be an
orientably-regular embedding of a complete graph $K_{r}^{(t)}$ of order $r\geq
2$ with edge-multiplicity $t\geq 1$, and let $G={\rm Aut}^{+}{\cal M}=\langle
x,y\ |\ x^{m},y^{n},(xy)^{2},\ldots\rangle$. In this situation one has $n=dt$
for $d=r-1$, with $N=\langle y^{d}\rangle\triangleleft G$, and the quotient
map determined by the group $H=G/N=\langle u,v\ |\
u^{\ell},v^{d},(uv)^{2},...,\rangle$ for $u=xN$ and $v=yN$ is an orientably-
regular embedding of the (simple) complete graph $K_{r}$. Orientably-regular
embeddings of the latter have been classified in [11]; it turns out that their
order is necessarily some prime power $q$ and they are of type $\\{\ell,d\\}$,
where $d=q-1$ and the values of $\ell$ are as follows: $\ell=q$ if
$q\in\\{2,3\\}$, $\ell=q-1$ if $q$ is even but $q\neq 2$ or $q\equiv 1$ mod
$4$, and $\ell=(q-1)/2$ if $q\equiv 3$ mod $4$ but $q\neq 3$. Moreover, the
group of orientation-preserving automorphisms of such a map turns out to be
isomorphic to ${\rm AGL}(1,q)$, the affine general one-dimensional groups over
finite fields of order $q$.

Our goal is to classify orientably-regular embeddings ${\cal M}={\cal M}(q,t)$
of complete graphs of order $q$ with edge-multiplicity $t$ for an arbitrary
given prime power $q$ and a positive integer $t$. If such a map is of type
$\\{m,n\\}$, with $n=dt=(q-1)t$, it would be natural to try to identify the
maps in terms of their groups $G={\rm Aut}^{+}{\cal M}(q,t)=\langle x,y\ |\
x^{m},y^{n},(xy)^{2},...\rangle$ by lifting presentations of their quotients
$G/N$ for $N=\langle y^{d}\rangle$ as given by (2). Since $K_{q}$ is not
bipartite for $q>2$, in (2) one then has $f=1$, which means that $N$ is a
central subgroup of $G$, making the extension of the quotient $G/N$ central
for $q>2$.

The process of lifting, however, assumes knowledge of presentations of the
quotient automorphism groups $H_{q}=\langle u,v\ |\
u^{\ell},v^{d},(uv)^{2},...,\rangle\cong{\rm AGL}(1,q)$ of orientably-regular
embeddings of the corresponding simple complete graphs, which appear to be
known only for $q\leq 5$ from [6] as part of a classification of regular maps
with underlying graphs of order at most $5$. It should be emphasised that the
classification of orientably-regular embeddings of simple complete graphs of
[11], although deep and taken advantage of a number of times here, is not in
terms of group presentations, and hence cannot be directly used for lifting.

Because of this state-of-the-art, in the next section we will use the
classification of [11] to determine all the orientably-regular maps with
simple complete underlying graphs in terms of presentations of their
automorphism groups.

##  4 Presentations of automorphism groups of
orientably-regular simple complete maps

Let $q=p^{k}$ be an arbitrary prime power and let $F_{q}$ be a finite field of
order $q$. The group $H_{q}=\langle u,v\rangle\cong{\rm AGL}(1,q)$ is a split
extension of its additive (and characteristic) subgroup
$F_{q}^{+}\cong(F_{p}^{+})^{k}$ of $F_{q}$ by its multiplicative group
$F^{\times}_{q}$; the subgroup $F_{q}^{+}$ is, at the same time, the
commutator subgroup of $H$. Let
$\mu=\mu(\lambda)=\lambda^{k}+a_{k-1}\lambda^{k-1}+\ldots+a_{1}\lambda+a_{0}$
be a monic primitive polynomial for the field $F_{q}$ with coefficients in its
prime field $F_{p}$, that is, a monic irreducible polynomial with roots
$\\{\xi^{p^{i}};\ 0\leq i\leq k-1\\}$ for some primitive element $\xi\in
F_{q}^{\times}$ (or, still equivalently, an irreducible factor of the
corresponding cyclotomic polynomial over $F_{q}$). There are $\varphi(q-1)/k$
such primitive polynomials, and it follows from [11] and also from arguments
in [10] that these polynomials are in a one-to-one correspondence with
isomorphism classes of orientably-regular embeddings of the graph $K_{q}$.

Recall that there is a standard way to associate a $k\times k$ matrix over
$F_{p}$ (equivalently, a linear transformation of $(F_{p}^{+})^{k}$ regarded
as a $k$-dimensional vector space over $F_{p}$) the minimal polynomial of
which is equal to the polynomial $\mu$ chosen above. For our purposes it will
be of advantage to consider the transpose of the standard companion matrix and
associate with $\mu$ the matrix $A$ defined by

$A=\left(\begin{array}[]{ccccccc}0&0&0&...&0&0&-a_{0}\\\
1&0&0&...&0&0&-a_{1}\\\ 0&1&0&...&0&0&-a_{2}\\\ &...&&...&&&...\\\
0&0&0&...&1&0&-a_{k-2}\\\ 0&0&0&...&...&1&-a_{k-1}\end{array}\right)$ (3)

with ${\rm det}(\lambda I-A)=\mu(\lambda)$. Primitivity of $\mu$ implies that
$A$ has order $q-1$ and every element of $H_{q}\cong F_{q}^{+}\rtimes
F_{q}^{\times}\cong{\rm AGL}(1,q)$ has the form $(g,A^{i})$ for some
$i\in\\{0,1,\ldots,q-2\\}$ and $g\in(F_{p}^{+})^{k}$, regarded as a
$k$-dimensional column vector, with multiplication in the semidirect product
given by $(g,A^{i})\cdot(h,A^{j})=(g+A^{i}h,A^{i+j})$. (Note that this
description of a semidirect product harmonises with multiplication of column
vectors by matrices from the left and with using the transpose of a companion
matrix.) In what follows we will denote by $\mathbf{0}$ the all-zero column
vector of dimension $k$, and for $1\leq i\leq k$ we will use the standard
notation $\mathbf{e}_{i}\in(F_{p}^{+})^{k}$ for the $i$-th unit column vector
of dimension $k$. Also, let $\mathbf{a}\in(F_{p}^{+})^{k}$ denote the column
vector forming the last column of $A$.

With this notation we are in position to state a further consequence of [11],
which is that for the generators $u$ and $v$ of the group $H_{q}\cong{\rm
Aut}^{+}{\cal M}$ one may take

$u=(\mathbf{e}_{1},-A^{-1})\ \ \mbox{and}\ \ v=(\mathbf{0},A),\ \ \mbox{with}\
\ uv=(\mathbf{e}_{1},-I)$ (4)

and routine calculations (see [10] for more details) imply that the order of
$u$ is $q-1$ if $q$ is a power of $2$ or $q\equiv 1$ mod $4$, and $(q-1)/2$ if
$q\equiv 3$ mod $4$; the orders of $v$ and $uv$ are $q-1$ and $2$,
respectively. In addition, one may verify that

$A\mathbf{e}_{i}=\mathbf{e}_{i+1}\ \ \ (1\leq i\leq k-1)\ \ \mbox{and}\ \
A\mathbf{e}_{k}=\mathbf{a}$ (5)

and, consequently,

$A^{i-1}(A-I)\mathbf{e}_{1}=\mathbf{e}_{i+1}-\mathbf{e}_{i}\ \ (1\leq i\leq
k-1)\ \ \mbox{and}\ \ A^{k-1}(A-I)\mathbf{e}_{1}=\mathbf{a}-\mathbf{e}_{k}\ .$
(6)

The way $u$ and $v$ have been introduced together with equations (6) imply
that
$u^{-1}v^{-1}uv=[u,v]=((A-I)\mathbf{e}_{1},I)=(\mathbf{e}_{2}-\mathbf{e}_{1},I)$,
and a similar calculation shows that

$v^{i-1}[u,v]v^{1-i}=(A^{i-1}(A-I)\mathbf{e}_{1},I)=(\mathbf{e}_{i+1}-\mathbf{e}_{i},I),\
\ 1\leq i\leq k-1,\ \ $ (7)

together with

$v^{k-1}[u,v]v^{1-k}=(A^{k-1}(A-I)\mathbf{e}_{1},I)=(\mathbf{a}-\mathbf{e}_{k},I)\
.$ (8)

Let $v_{q}=1$ if $q$ is even, and $v_{q}=v^{(q-1)/2}$ if $q$ is odd. We now
prove by induction that

$(\mathbf{e}_{i},I)=v^{i-1}(uv)v^{1-i}v_{q}\ \ \mbox{for every}\ \
i\in\\{1,2,\ldots,k\\}\ .$ (9)

For even $q$ one has (9) for $i=1$ trivially, and for odd $q$, from
$v^{(q-1)/2}=(\mathbf{0},-I)$ it follows that $(uv)v_{q}=(\mathbf{e}_{1},I)$,
which is again (9) for $i=1$. The induction hypothesis, that is,
$v^{i-1}(uv)v^{1-i}v_{q}=(\mathbf{e}_{i},I)$ for $i\geq 1$ and $i\leq k-1$,
together with (7) implies that

$(\mathbf{e}_{i+1},I)=(\mathbf{e}_{i+1}-\mathbf{e}_{i},I)\cdot(\mathbf{e}_{i},I)=v^{i-1}[u,v]v^{1-i}\cdot
v^{i-1}(uv)v^{1-i}v_{q}$

and the last expression is easily seen to simplify to $v^{i}(uv)v^{-i}v_{q}$,
completing the induction step. By almost the same token, combining (8) with
the case $i=k$ of (9) gives

$(\mathbf{a},I)=(\mathbf{a}-\mathbf{e}_{k},I)\cdot(\mathbf{e}_{k},I)=v^{k-1}[u,v]v^{1-k}\cdot
v^{k-1}(uv)v^{1-k}v_{q}=v^{k}(uv)v^{-k}v_{q}\ .$ (10)

Observe that (9) also implies that the elements $v^{i-1}(uv)v^{1-i}v_{q}$ for
$i\in\\{1,2,\ldots,k\\}$ commute with each other; this feature can be
expressed in a unified form by the relations
$[uvv_{q},v^{i}(uvv_{q})v^{-i}]=1$ for $i\in\\{1,2,\ldots,k-1\\}$; note also
that $(uvv_{q})^{p}=1$.

Finally, linear dependence of the $k+1$ vectors
$\\{\mathbf{e}_{1},\ldots,\mathbf{e}_{k},\mathbf{a}\\}$ implies that
$(\mathbf{0},I)=(\mathbf{a},I)\prod_{i=1}^{k}\ (\mathbf{e}_{i},I)^{a_{i-1}}$.
By (9) and (10) this last equation translates to the relation

$v^{k}(uvv_{q})v^{-k}\prod_{i=0}^{k-1}\left(v^{i}(uvv_{q})v^{-i}\right)^{a_{i}}=1\
.$ (11)

For our primitive polynomial
$\mu=\mu(\lambda)=\lambda^{k}+a_{k-1}\lambda^{k-1}+\ldots+a_{1}\lambda+a_{0}$,
let $W(u,v;\mu)$ denote the left-hand side of (11); that is, we let

$W(u,v;\mu)=v^{k}(uvv_{q})v^{-k}\prod_{i=0}^{k-1}\left(v^{i}(uvv_{q})v^{-i}\right)^{a_{i}}$
(12)

Collecting all the information gathered so far, we have identified the
following relators in a presentation of the group $H_{q}=\langle
u,v\rangle\cong{\rm AGL}(1,q)$ for an arbitrary prime power $q=p^{k}$, with
$\mu$ and $W$ as above, and with $\ell=q$ if $q\in\\{2,3\\}$, $\ell=q-1$ if
$q$ is even ($q\neq 2$) or $q\equiv 1$ mod $4$, and $\ell=(q-1)/2$ if $q\equiv
3$ mod $4$ but $q\neq 3$:

$\displaystyle\mbox{$4$ relators determining orders of elements:}\ \ v^{q-1},\
(uv)^{2},\ u^{\ell},\ (uvv_{q})^{p},$ (13) $\displaystyle\mbox{$k-1$
commutativity relators:}\ \ [uvv_{q},v^{i}(uvv_{q})v^{-i}],\ 1\leq i\leq k-1,\
\ \mbox{and}$ (14) $\displaystyle\mbox{the relator implied by linear
dependence:}\ \ W(u,v;\mu)\ .$ (15)

Recall that $v_{q}=1$ for even $q$, and in this case the relator
$(uvv_{q})^{p}$ is redundant. There may be other redundancies for general $q$
but we will not investigate possibilities of further simplifications, except
when $k=1$. In this case, there are no commutativity relators and the
presentation found so far for $q=p$ and any primitive element $\xi\in F_{p}$,
regarded as an integer mod $p$, reduces to

$\langle u,v\ |\
u^{\ell},v^{p-1},(uv)^{2},(uv^{(p+1)/2})^{p},v^{(p+1)/2}u(uv^{(p+1)/2})^{\xi}\rangle\
.$ (16)

We now show that the presentation given by (13) – (15) determines a group
isomorphic to ${\rm AGL}(1,q)$.

###### Theorem 2

Let $p$ be an arbitrary prime, let $k$ be a positive integer, and let
$\mu=\mu(\lambda)=\lambda^{k}+a_{k-1}\lambda^{k-1}+\ldots+a_{1}\lambda+a_{0}$
be a monic primitive polynomial for a finite field of order $q=p^{k}$ with
coefficients in the corresponding prime field. Further, let Rels denote the
collection of $k+4$ relators comprising the four relators from (13), the $k-1$
relators from (14) and the single relator from (15) that depends on $\mu$.
Then, the group determined by the presentation $\langle u,v\ |\ {\rm
Rels}\rangle$ is isomorphic to ${\rm AGL}(1,q)$.

Proof. Let $H=H_{q}=\langle u,v\ |\ {\rm Rels}\rangle$. The derivation of the
relators (13) – (15) implies that ${\rm AGL}(1,q)$ is definitely a quotient
group of $H$; in particular, the subgroup generated by $v$ is isomorphic to
$C_{q-1}$. Observe also that there is an epimorphism $\vartheta:\ H\to\langle
v\rangle$ given by $\vartheta(u)=v_{q}v^{-1}$ and $\vartheta(v)=v$, or,
equivalently, $\vartheta(uv)=v_{q}$ and $\vartheta(v)=v$; this follows from
the fact that $\vartheta$ maps all the relators from the presentation of $H$
either to the identity or to the relator $v^{q-1}$ defining $C_{q-1}$. Let $L$
be the kernel of $\vartheta$; it follows that $H/L\cong C_{q-1}$ and
$|H/L|=q-1$. Since ${\rm AGL}(1,q)$ is a quotient of $H$, the order of $L$
must be an integer multiple of $q$, and so our task will be accomplished if we
show that $|L|=q$.

To do so, we will use the Reidemeister-Schreier method to determine a
presentation for $L$. The method is well known and here we just adapt its
brief description from [15] to our situation, which simplifies because here
$L$ is a normal subgroup of $H$.

We begin with setting up a Cayley digraph $D={\rm Cay}(H/L)$ for the group
$H/L$ and the generating set $\\{Lu,Lv\\}$, which we may for simplicity
identify with $\\{u,v\\}$; arcs of $D$ will be labelled by the corresponding
generators and we will briefly refer to them as $u$-arcs and $v$-arcs. The
$q-1$ vertices of $D$, each of in- and out-degree $2$, represent the $q-1$
right cosets $Lv^{i}$, $0\leq i\leq q-2$; instead of $Lv^{i}$ we will simply
write $i$ in what follows. Observe that $D$ contains a directed Hamilton cycle
formed by the $v$-arcs $(Lv^{i},Lv^{i+1})$, or, in a simplified notation,
$(i,i+1)_{v}$ for $i\in\\{0,1,\ldots,q-2\\}$, with $(i+1,i)_{v}$ being their
reverses. As regards $u$-arcs, from $\vartheta(uvv_{q})=1$ it follows that
$uvv_{q}\in L$, and since $L\triangleleft H$ one also has
$v^{i}(uvv_{q})v^{-i}\in L$, $1\leq i\leq q-2$. The last containment relation
is equivalent to $(Lv^{i})u=Lv^{i-1}v_{q}$, which means that from every vertex
$Lv^{i}$ there emanates a $u$-arc terminating at the vertex $Lv^{i-1}v_{q}$
which reduces to $Lv^{i+(q-3)/2}$ for $q$ odd (with exponents to be read mod
$q-1$) and to $Lv^{i-1}$ for $q$ even. Letting $\overline{q}=(q-1)/2$ for $q$
odd and $\overline{q}=0$ for $q$ even, such $u$-arcs will be simply denoted
$(i,i-1+\overline{q})_{u}$ for both parities of $q$. This completes the
description of all arcs in our digraph $D$.

Observe that if $q$ is even, with $v_{q}=1$, this means that in the digraph
$D$ for every $v$-arc $(i-1,i)_{v}$ one also has a $u$-arc $(i,i-1)_{u}$ in
the direction reverse to $v$ (when $q=2$, the digraph has a single vertex with
two loops). If $q=3$, the digraph has just $2$ vertices joined by a pair of
mutually oppositely directed $v$-arcs, with a $u$-loop at each vertex. If
$q=5$, then with every $v$-arc $(i,i+1)_{v}$ there is a parallel $u$-arc
$(i,i+1)_{u}$. In all the remaining cases $D$ is a simple digraph, without
loops and parallel arcs, containing another Hamilton cycle formed by $u$-arcs
if $q\equiv 1$ mod $4$, and a pair of cycles of length $\overline{q}$
consisting of $u$-arcs if $q\equiv 3$ mod $4$.

The next step is choosing a (directed) spanning tree $T$ of $D$, which, in our
case, will be formed by the Hamilton path consisting of the $q-2$ $v$-arcs
$(i,i+1)_{v}$, $0\leq i\leq q-3$ (the tree will have a single vertex in the
trivial case when $q=2$). With this choice of $T$, the $q$ cotree arcs
comprise the $q-1$ $u$-arcs described above and the single $v$-arc
$(q-2,1)_{v}$. For $0\leq i\leq q-2$, each $u$-arc $e_{i}$ from $Lv^{i}$ to
$Lv^{i-1}v_{q}$ is contained in a unique closed walk in $T+e_{i}$, emanating
from and terminating at the vertex $L$ (identified with $0$). For odd $q$ this
walk has the form $P_{i}C_{i}P_{i}^{-1}$, where the closed walk $C_{i}$
(consisting just of a loop if $q=3$) and the open walk $P_{i}$ (with $P_{0}$
reducing to the vertex $0$) consist of arcs as follows:

$C_{i}=(i,i-1+\overline{q})_{u}\,(i-1+\overline{q},i-2+\overline{q})_{v}\,...\,(i+1,i)_{v}\
\ {\rm and}\ \ P_{i}=(0,1)_{v}\,...\,(i-1,i)_{v}\ .$

If $q$ is even, then the unique closed walk has the form
$P_{i}C_{i}P_{i}^{-1}$, with $P_{i}$ as above and
$C_{i}=(i,i-1)_{u}\,(i-1,i)_{v}$.

By Reidemeister-Schreier, for $i\in\\{0,1,\ldots,q-2\\}$, products of labels
of arcs as they are encountered (in either direction) in the course of
traversing the closed walk $P_{i}C_{i}P_{i}^{-1}$ constitute the so-called
Schreier generators for $L$. In our case, if $q$ is odd, traversing the walk
$P_{i}C_{i}P_{i}^{-1}$ gives the product
$v^{i}u(v^{-1})^{\overline{q}-1}v^{-i}=v^{i}(uvv_{q})v^{-i}$, and if $q$ is
even (and $v_{q}=1$), then the traversal yields the product $v^{i}(uv)v^{-i}$.
It follows that for both parities of $q$ the $q-1$ $u$-arcs induce $q-1$
Schreier generators of the form $g_{i}=v^{i}(uv)v_{q}v^{-i}$ for
$i\in\\{0,1,\ldots,q-2\\}$; note that they are mutually conjugate. The only
$v$-arc not in $T$ is the arc $(v^{q-2},v)$ and because of $v^{q-1}=1$ it
induces the identity element of $L$ as the last (and obviously redundant)
Schreier generator. The important fact implied by Reidemeister-Schreier method
is that $\\{g_{i}\ |\ 0\leq i\leq q-2\\}$ is a generating set for the group
$L$.

It remains to determine new relators for a presentation of $L$. Normality of
$L$ enables us to reduce the Reidemeister-Schreier process to considering only
those closed walks representing relators in (13) – (15) in the Cayley digraph
$D$ which start (and end) at the vertex $L$, with the goal of rewriting each
original relator in terms of Schreier generators. But since we know from the
beginning that the order of $L$ is a multiple of $q$, it will suffice to apply
the process to a suitable subset of original relators, namely, to the last
relator of (13) and to all of (14) and (15). These can be rewritten in terms
of our Schreier generators in a straightforward way by inspection, which
results in the following collection of $k+1$ new relators: a single relator
$g_{0}^{p}$ arising from the last relator in of (13), $k-1$ relators
$[g_{0},g_{i}]$ for $i\in\\{1,2,\ldots,k-1\\}$ arising from (14), and a single
relator $g_{k}\prod_{i=0}^{k-1}(g_{i})^{a_{i}}$ coming from (15) in which
exponents are coefficients of the minimal polynomial $\mu$.

A repeated application of conjugation by $v$ to the relators $[g_{0},g_{i}]$
for $i\in\\{1,2,\ldots,k-1\\}$ shows that elements of the set $S_{k}=\\{g_{i}\
|\ 0\leq i\leq k-1\\}$ of the first $k$ mutually conjugate Schreier generators
commute with each other, and each of them has order $p$ because of the relator
$g_{0}^{p}$. The relator involving coefficients of $\mu$ enables one to write
$g_{k}$ by means of generators in $S_{k}$, and by induction (again using
repeated conjugation by $v$) it follows that each of the $q-1$ non-identity
Schreier generators can be expressed in terms of elements of $S_{k}$. This
shows that $L$ is Abelian and generated by $S_{k}$; as a consequence, $L$ has
exponent $p$, and so $|L|\leq p^{k}=q$. Since we have established that
$|L|\geq q$ at the beginning, it follows that $|L|=q$ and $L\cong C_{p}^{k}$.
(Note that here the set of all Schreier generators of $L$ found by the
Reidemeister-Schreier method coincides with the entire group $L$.) $\Box$

##  5 Automorphism groups of orientably-regular
embeddings of complete multigraphs

Let $q=p^{k}$ be a prime power and let ${\cal M}(q,t)$ be an orientably-
regular map with underlying graph $K_{q}^{(t)}$. In section 3 we saw that for
$q>2$ the group $G_{q,t}=\langle x,y\rangle\cong{\rm Aut}^{+}{\cal M}(q,t)$ is
a central extension of the group $H_{q}\cong{\rm AGL}(1,q)$ by the cyclic
group $N=\langle y^{q-1}\rangle$ of order $t$. We begin by a more general
observation about such central extensions.

###### Proposition 1

For $q=p^{k}$ and $s\geq 1$ let $G$ be a group containing an element $y$ of
order $(q-1)s$ such that $N=\langle y^{q-1}\rangle$ is a central subgroup of
$G$, with $G/N\cong{\rm AGL}(1,q)$. If $q=4$, the commutator subgroup
$G^{\prime}$ of $G$ satisfies $|G^{\prime}\cap N|\leq 2$; if $q\neq 4$, then
$G^{\prime}\cong C_{p}^{k}$ and $G^{\prime}\cap\langle y\rangle=1$.

Proof. By a result of [18] on central and commutator subgroups of a group, the
intersection $N\cap G^{\prime}$ embeds in the Schur multiplier $M(G/N)\cong
M({\rm AGL}(1,q))$. Luckily, the latter is known to be trivial for every
$q\neq 4$, and isomorphic to $C_{2}$ if $q=4$, cf. [8]. It follows that for
$q\neq 4$ one has $|G^{\prime}\cap N|=1$, implying that the normal subgroup
$G^{\prime}N$ of $G$ has order $|G^{\prime}|s$ in this case, while
$|G^{\prime}\cap N|\leq 2$ for $q=4$.

This enables us to specify $G^{\prime}$ for $q\neq 4$. The commutator subgroup
$(G/N)^{\prime}$ of $G/N\cong{\rm AGL}(1,q)$ is known to be isomorphic to
$C_{p}^{k}$, of order $q=p^{k}$. Combining the well-known formula
$(G/N)^{\prime}\cong G^{\prime}N/N$ with the conclusion
$|G^{\prime}N|=|G^{\prime}|s$ for $q\neq 4$ gives
$q=|(G/N)^{\prime}|=|G^{\prime}N|/|N|=|G^{\prime}|s/s=|G^{\prime}|$, so that
$|G^{\prime}|=q$ if $q\neq 4$. Also, as $N\cap G^{\prime}$ is trivial, from
$(G/N)^{\prime}\cong G^{\prime}N/N$ it follows that $(G/N)^{\prime}\cong
G^{\prime}$ and hence $G^{\prime}\cong C_{p}^{k}$ if $q\neq 4$.

To finish the proof for $q\neq 4$, we extend the finding that $G^{\prime}$
intersects trivially with $N$ to showing that $G^{\prime}\cap\langle
y\rangle=1$; we may clearly also assume that $q\neq 2$. Suppose that $y^{j}\in
G^{\prime}$ for some positive integer $j<(q-1)s$ which is not divisible by
$q-1$. Then, the order of $y^{j}$, which is equal to
$(q-1)s/\gcd\\{(q-1)s,j\\}$, must divide $q=|G^{\prime}|$. But since $q-1$ and
$q$ are coprime, the denominator $\gcd\\{(q-1)s,j\\}$ must be divisible by
$q-1$ and $j$ would have to be a multiple of $q-1$, a contradiction with
triviality of $G^{\prime}\cap N$. $\Box$

We will need Proposition 1 as a stand-alone statement later. As the next step
we prove a more specific version of this result, related to the maps ${\cal
M}(q,t)$ and the associated groups $G_{q,t}={\rm Aut}^{+}{\cal M}(q,t)$. Here
we will refer to the presentation of the quotient $H_{q}=\langle u,v\rangle$
of $G_{q,t}$ defined by means of the relators listed in (13) – (15).

###### Proposition 2

Let $G=G_{q,t}=\langle x,y\rangle$ for $q=p^{k}$, with a central subgroup
$N=\langle y^{q-1}\rangle\cong C_{t}$ such that $G/N\cong H_{q}=\langle
u,v\rangle$, where $u=Nx$ and $v=Ny$, with presentation defined by (13) – (15)
using a primitive polynomial $\mu$ over $F_{q}$. If $q\neq 4$, then
$G^{\prime}\cong C_{p}^{k}$ and $G^{\prime}\cap\langle y\rangle=1$. In
particular, $G$ is then isomorphic to a split extension of the elementary
abelian group $C_{p}^{k}$ by a cyclic group of order $(q-1)t$, in which the
action of $\langle y\rangle$ on $C_{p}^{k}$ is given by $y^{j}\mapsto A^{j}$,
where $A$ is the associated matrix of the primitive polynomial $\mu$ from (3).

Proof. The first statement follows from Proposition 1 for $s=t$. This also
implies that $G$ is a split extension of its subgroup $G^{\prime}\cong
C_{p}^{k}$ by the cyclic subgroup $\langle y\rangle<G$, of order $(q-1)t$. It
remains to specify the conjugation action of $\langle y\rangle$ on
$G^{\prime}$ that determines the extension, that is, the corresponding group
homomorphism $\theta:\ \langle y\rangle\to{\rm Aut}(C_{p}^{k})\cong{\rm
GL}(k,p)$. Since $N=\langle y^{q-1}\rangle$ is central in $G$, it follows that
the value of $\theta$ on the coset $\bar{y}=Ny$ is constant. At the same time,
the action of $\langle y\rangle$ on $G^{\prime}$ in the group $G$ projects
onto the action of $\langle\bar{y}\rangle$ on $G/N$ (which is still isomorphic
to $G^{\prime}$) in the factor group $G/N\cong H_{q}\cong
C_{p}^{k}\rtimes\langle\bar{y}\rangle$. But the latter action is generated by
$\bar{y}\mapsto A$ for the matrix $A$ associated with $\mu$, which allows one
to conclude that $\theta(y^{j})=A^{j}$ for every $j$ mod $(q-1)t$. $\Box$

While the extension $C_{p}^{k}\rtimes C_{(q-1)t}$ for $q\neq 4$ is uniquely
determined as an abstract group (for a given matrix $A$), this does not
necessarily mean that it uniquely determines a map ${\cal M}(q,t)$ with ${\rm
Aut}^{+}{\cal M}(q,t)=\langle x,y\rangle$. Theorem 3 and Proposition 3 will
show that there may exist several distinct choices of elements $x$ with the
same coset $\bar{x}=Nx$ but giving non-isomorphic maps defined by distinct
generating pairs $(x,y)$ for $y$ as in Proposition 2.

By the theory outlined in the introduction, the map ${\cal M}(q,t)$ is a
$t$-fold branched cover of an orientably-regular embedding ${\cal M}_{q}$ of a
simple complete graph of order $q$, and if $q>2$, isomorphism classes of the
maps ${\cal M}_{q}$ are in one-to-one correspondence with primitive
polynomials over $F_{q}$. Choose such a polynomial
$\mu=\mu(\lambda)=\lambda^{k}+a_{k-1}\lambda^{k-1}+\ldots+a_{1}\lambda+a_{0}$
and, as before, let $W(u,v;\mu)$ be given by (12). Also, we keep $\ell$ equal
to $q-1$ if $q$ is even or $q\equiv 1$ mod $4$, and equal to $(q-1)/2$ if
$q\equiv 3$ mod $4$, save the exceptional case $\ell=3$ for $q=3$. Theorem 2
combined with the ‘lifting’ method from (2) imply that for $q>2$ the group
$G_{q,t}={\rm Aut}^{+}{\cal M}(q,t)$ admits a presentation of the form

$G_{q,t}=\langle x,y\ |\ y^{(q{-}1)t},\,(xy)^{2},\,[x,y^{q{-}1}],\,{\rm
Rel}_{1},\,{\rm Rel}_{2},\,{\rm Rel}_{3}\,\rangle$ (17)

where the collections of relators ${\rm Rel}_{1}$, ${\rm Rel}_{2}$ and ${\rm
Rel}_{3}$ are obtained, respectively, from the relators in (13), (14) and (15)
as follows. First, we skip the first two relators of (13) because their new
versions appear in (17). Then, we substitute $x$ for $u$, $y$ for $v$, and
$y_{q}=y^{(q-1)/2}$ for the value of $v_{q}$ if $q$ is odd (with
$y_{q}=v_{q}=1$ for $q$ even) in each of the remaining relators of (13) –
(15). Finally, to each of the resulting words (in $x$ and $y$) arising from
such substitutions we append a multiplicative factor consisting of some power
of $y^{1-q}$. In our notation, the multiplicative factors will have the form
$y^{(1-q)\omega}$ for $\omega\in\\{a,b,c,e_{1},\ldots,e_{k-1}\\}$ mod $t$, and
hence the collection of relators in the presentation (17) will be as follows:

$\displaystyle\mbox{${\rm Rel}_{1}$:}\ \ x^{\ell}\cdot y^{(1{-}q)a},\
(xyy_{q})^{p}\cdot y^{(1{-}q)b};$ (18) $\displaystyle\mbox{${\rm Rel}_{2}$:}\
\ [xyy_{q},y^{i}xyy_{q}y^{-i}]\cdot y^{(1{-}q)e_{i}},\ 1\leq i\leq k-1;$ (19)
$\displaystyle\mbox{${\rm Rel}_{3}$:}\ \ W(x,y;\mu)\cdot y^{(1{-}q)c}\ .$ (20)

Recall that $y_{q}=1$ for even $q$; note also that the value of $f$ appearing
in (2) is here equal to $1$ since our underlying graphs for $q>2$ are not
bipartite.

We will determine the parameters $a$, $b$, $c$ and $e_{i}$ ($1\leq i\leq k-1$)
mod $t$, under the assumptions that $q>4$ and $|G_{q,t}|=q(q-1)t$, which is
the expected order of the group ${\rm Aut}^{+}{\cal M}(q,t)$.

###### Theorem 3

For a prime power $q=p^{k}>4$ let $G=\langle x,y\rangle$ be a group with a
presentation given by (17) – (20), and for odd $p$ let $\alpha=\alpha(\mu)$ be
the unique even integer in the set
$\\{1,\ldots,p-1\\}\cup\\{p+1,\ldots,2p-1\\}$, equal mod $p$ to the sum of the
coefficients of the primitive polynomial $\mu$. If the order of $G$ is
$q(q-1)t$, then the following holds:

(I) If $q$ is odd, then $t$ is also odd, and mod $t$ one has $e_{i}=0$ ($1\leq
i\leq k-1$), $a=-1$ for $q\equiv 1$ mod $4$ while $a=(t-1)/2$ for $q\equiv 3$
mod $4$, $b=(p+t)/2$, and $c=\alpha/2$.

(II) If $q$ is even, then $b=e_{i}=0$ ($1\leq i\leq k-1$) for every $t\geq 1$;
moreover, if $t$ is odd, then $(a,c)=(-1,0)$, and if $t$ is even, then
$(a,c)\in\\{(-1,0),(t/2-1,t/2)\\}$, all mod $t$.

Conversely, if $G$ is a group with presentation (17) – (20) in which $q>4$ and
the parameters $t$, $a$, $b$, $c$ and $e_{i}$ satisfy (I) for $q$ odd and (II)
for $q$ even, then $G$ has order $q(q-1)t$.

Proof. Let $G$ be a group presented as in (17) and assume that its order is
$q(q-1)t$. Clearly, $N=\langle y^{q-1}\rangle$ is a central subgroup of $G$;
by Theorem 2 and the assumption on the order of $G$ one has $|N|=t$, and the
order of $y$ is $(q-1)t$. Further, we know that the quotient $G/N$ is
isomorphic to $H_{q}\cong{\rm AGL}(1,q)$. For $q>4$, Proposition 2 implies
that $|G^{\prime}|=q$ and $G^{\prime}\cap\langle y\rangle$ is trivial; hence
the normal subgroup $G^{\prime}N$ of $G$ has order $|G^{\prime}|t$.

Thus, the abelianisation $G/G^{\prime}$ is isomorphic to $\langle
y\rangle\cong C_{(q-1)t}$. In what follows we let $\bar{x}=G^{\prime}x$ and
identify $y$ with $G^{\prime}y$ (which we may do as no non-trivial power of
$y$ is in $G^{\prime}$); also, we let $i$ extend over the set
$\\{1,\ldots,q-1\\}$. Our first version of the induced presentation of
$G/G^{\prime}$, obtained only by absorbing commutators in (19), has the form

$\langle\bar{x},y\ |\
y^{(q{-}1)t},\,(\bar{x}y)^{2},\,(\bar{x})^{\ell}y^{(1{-}q)a},\,(\bar{x}yy_{q})^{p}y^{(1{-}q)b},\,\ldots,\,y^{(1-q)e_{i}},\,\ldots,\,\,W(\bar{x},y;\mu)y^{(1-q)c}\,\rangle$
(21)

The facts that the order of $y$ in (21) is equal to $(q-1)t$ (by our
assumption that $|G_{q,t}|=q(q-1)t$) together with $[\bar{x},y]=1$ enable us
to determine the parameters $a,b,c$ and $e_{i}$ ($1\leq i\leq k-1$) from (21)
quite conveniently. For example, because of the order of $y$, presence of the
relators $y^{(1-q)e_{i}}$ in (21) implies that $(q-1)t\mid(q-1)e_{i}$ and
hence $e_{i}\equiv 0$ mod $t$ for every $i\in\\{1,\ldots,k-1\\}$. The
remaining parameters, in the order $b$, $a$ and $c$, will be calculated in the
next three steps.

Step 1: the value of $b$. Observe that the relator
$(\bar{x}yy_{q})^{p}y^{(1{-}q)b}$ for even $q$ collapses to $y^{(1{-}q)b}$,
implying that $b\equiv 0$ mod $t$, with no restriction on the parity of $t$.
For odd $q$, with the help of $(\bar{x}y)^{p}=\bar{x}y$ in $G/G^{\prime}$ the
same relator reduces to $(\bar{x}y)\cdot y^{p(q-1)/2}\cdot y^{(1-q)b}$ and
hence gives $\bar{x}y=y^{(2b-p)(q-1)/2}$. Since $G^{\prime}$ has odd order for
odd $q$, the element $\bar{x}y$ has order $2$ in $G/G^{\prime}$ and so
$y^{(2b-p)(q-1)/2}$ must be an involution in the group
$G/G^{\prime}\cong\langle y\rangle$. As the latter contains a single
involution $y^{(q-1)t/2}$, it follows that $(q-1)t/2$ divides $(2b-p)(q-1)/2$
and so $t\mid(2b-p)$. In particular, if $q$ is odd, then so is $t$, and one
may take $b=(p+t)/2$.

Step 2: the value of $a$. To calculate $a$ from the relator
$(\bar{x})^{\ell}y^{(1{-}q)a}$, we begin with odd $q$. If $q\equiv 1$ mod $4$,
then $\ell=q-1$ is even and so $(\bar{x}y)^{q-1}=1$ in $G/G^{\prime}$, which
reduces the relator to $y^{(1{-}q)(a+1)}$, and by the order of $y$ we conclude
that $a\equiv-1$ mod $t$. If $q\equiv 3$ mod $4$, then $\ell=(q-1)/2$ is odd
and the relator is equivalent to
$(\bar{x})^{(q-1)/2}y^{(1-q)a}=(\bar{x}y)^{(q-1)/2}\cdot
y^{(1-q)a+(1-q)/2}=\bar{x}y\cdot y^{(1-q)a+(1-q)/2}$, and using the fact that
$\bar{x}y$ is an involution we obtain that $(q-1)t/2$ divides $(2a+1)(q-1)/2$
and so $2a+1\equiv 0$ mod $t$ (and one may take $a=(t-1)/2$, knowing that $t$
must be odd here). If $q$ is even, then $\ell=q-1$ is odd, and
$(\bar{x}y)^{q-1}=\bar{x}y$ in $G/G^{\prime}$. Now, $\bar{x}y$ has order $1$
or $2$ in $G/G^{\prime}$, depending on whether $xy\in G^{\prime}$ or not (and
both cases occur, as we shall see later). Accordingly, the relator we started
with reduces to $y^{(1{-}q)(a+1)}$ if $xy\in G^{\prime}$, and to
$\bar{x}y\cdot y^{(1{-}q)(a+1)}$ if $xy\notin G^{\prime}$. This implies that
$t\mid(a+1)$ in the first case, and $t\mid 2(a+1)$ but $t\nmid(a+1)$ in the
second case (for $t$ even), by calculations similar to the previous ones; in
particular, one may take $a=-1$ and $a=t/2-1$, respectively.

Step 3: the value of $c$. The relator
$W(\bar{x},y;\mu)=y^{k}(\bar{x}yy_{q})y^{-k}\prod_{i}y^{i}(\bar{x}yy_{q})^{a_{i}}y^{-i}\cdot
y^{(1-q)c}$ will enable us to determine $c$ by a successive abelianisation.
First, canceling conjugates by powers of $y$ gives
$(\bar{x}yy_{q})^{a(\mu)}y^{(1-q)c}$, where $\alpha=\alpha(\mu)$. Clearly,
$\alpha$ is not congruent to $0$ mod $p$, because of irreducibility of $\mu$.
If $q$ is even, that is, if $p=2$, then the last relator collapses to
$\bar{x}y\cdot y^{(1-q)c}$, leading to the conclusion that $t\mid c$ if $xy\in
G^{\prime}$ and $t\mid 2c$ but $t\nmid c$ if $xy\notin G^{\prime}$ (in which
case $t$ must be even). This means that if $xy\in G^{\prime}$, one may take
$c=0$ for every $t\geq 1$, and if $xy\notin G^{\prime}$, the element $xy$ has
order $2$ in $G/G^{\prime}$, forcing $t$ to be even, and then one may take
$c=t/2$. If $q$ is odd, then $\bar{x}y$ has order $2$ in $G/G^{\prime}$,
because $|G^{\prime}|=q$ is odd. As $\alpha$ mod $t$ is the unique even
integer between $2$ and $2t-2$, the relator
$(\bar{x}yy_{q})^{\alpha}y^{(1-q)c}$ further reduces to
$y^{\alpha(q-1)/2}y^{(1-q)c}=y^{(\alpha-2c)(q-1)/2}$, giving
$t\mid(\alpha/2-c)$, and one may take $c=\alpha/2$. (The reader may have
noticed that different choices of integers $\alpha=\alpha(\mu)$ mod $t$ for
odd $q$ would give different values of $c=c(\alpha)$, but in conjunction with
the relator $(\bar{x}yy_{q})^{p}y^{(1-q)b}$ it may be checked that any pair of
such choices determine equivalent presentations.)

For the converse, suppose that $G$ is given by the presentation (17) – (20) in
which the parameters $t$, $a$, $b$, $c$ and $e_{i}$ satisfying (I) for $q$ odd
and (II) for $q$ even. Let us now substitute these values in the corresponding
relators of (21) that define the abelianisation $G/G^{\prime}$, referring in
the process to our calculations in Steps 1 – 3. To begin with, note that that
all the relators in (21) containing $e_{i}$ simply vanish by letting
$e_{i}=0$, $1\leq i\leq k-1$.

By Step 1, the relator containing $b$ vanishes for $b=0$ if $q$ is even, and
gives $\bar{x}y=y^{t(q-1)/2}$ for $b=(p+t)/2$ if $q$ is odd, which implies
that $\bar{x}=y^{t(q-1)/2-1}\in\langle y\rangle$. By Step 2, the relator
involving the parameter $a$ vanishes for $q\equiv 1$ mod $4$ (when $a=-1$) and
gives $\bar{x}y=y^{t(q-1)/2}$ for $q\equiv 3$ mod $4$ (when $a=(t-1)/2$), so
that $\bar{x}=y^{t(1-q)/2-1}$ again. For $q$ even the analysis depended on
whether $xy\in G^{\prime}$ or not; if $xy\in G^{\prime}$, then $\bar{x}y=1$ in
$G/G^{\prime}$, so that $\bar{x}=y^{-1}$ (for $a=-1$ and every $t\geq 1$), and
if $xy\notin G^{\prime}$, then one arrives at $\bar{x}=y^{(q-1)(t/2)-1}$ for
$a=t/2-1$. Finally, by Step 3 the relator containing $c$ either vanishes or
implies that $\bar{x}=y^{t(q-1)/2-1}$, by reasoning analogous to those related
to Step 1 and 2. In all these cases the formulae for $\bar{x}$ show not only
that $\bar{x}\in\langle y\rangle$ but also that
$(\bar{x}y)^{2}=(\bar{x})^{2}y^{2}=1$.

It follows that for $a$, $b$, $c$ and $e_{i}$ given by (I) and (II), the
presentation (21) of the group $G/G^{\prime}$ collapses to $\langle y\ |\
y^{(q-1)t}\rangle$.

But observe that by the presentation (17) – (20) of the original group $G$,
the subgroup $N=\langle y^{q-1}\rangle$ is central in $G$, and one may check
against the list of relators in (13) – (15) that the induced presentation of
$G/N$ determines a group isomorphic to ${\rm AGL}(1,q)$. Applying Proposition
1 to this situation for $q>4$ gives $G^{\prime}\cap\langle y\rangle=1$ and
$|G^{\prime}|=q$. Taken together with the derived induced presentation of
$G/G^{\prime}$ one concludes that the order of $y$ is equal to $(q-1)t$ and
hence $|G|=q(q-1)t$, as claimed. This completes the proof. $\Box$

Thus, for an arbitrary prime power $q=p^{k}>4$ and an arbitrary integer $t\geq
1$, a complete graph $K_{q}^{(t)}$ of order $q$ and edge-multiplicity $t$
admits an orientably-regular embedding ${\cal M}$ if and only if $t$ and the
parameters $a$, $b$, $c$ and $e_{i}$ ($0\leq i\leq k-1$) appearing in (17) –
(20) are as stated in parts (I) and (II) of Theorem 3, in which case the group
${\rm Aut}^{+}({\cal M})$, of order $q(q-1)t$, admits a presentation given by
(17) – (20). For a given $q>4$ and a monic primitive polynomial $\mu$ over
$F_{q}$, this gives two maps if both $q$ and $t$ are even, which we will
denote ${\cal M}_{0}(q,t;\mu)$ and ${\cal M}_{1}(q,t;\mu)$, where the
subscripts correspond, respectively, to the values of $c=0$ and $c=t/2$ from
part (II) of Theorem 3, and a unique map for every odd $t\geq 1$ and an
arbitrary $q>4$, which we will denote ${\cal M}_{2}(q,t;\mu)$. It remains to
check for potential isomorphisms between these maps.

###### Theorem 4

Let $S$ be the set of ordered triples $(q,t;\mu)$, where $q>4$ is a prime
power, $t$ is a positive integer (odd if $q$ is odd), and $\mu$ is a monic
primitive polynomial over $F_{q}$. Among all maps ${\cal M}_{i}(q,t;\mu)$ for
$(q,t;\mu)\in S$ and $i\in\\{0,1,2\\}$, no two are isomorphic to each other.
In particular, the number of pairwise non-isomorphic orientably-regular
embeddings of $K_{q}^{(t)}$ for $q=p^{k}>4$ is equal to $\varphi(q-1)/k$ if
$t$ is odd, and $2\varphi(q-1)/k$ if both $q$ and $t$ are even.

Proof. Let $(q,t;\mu)$ and $(q^{\prime},t^{\prime};\mu^{\prime})$ be two
triples from $S$, and let ${\cal M}={\cal M}_{i}(q,t;\mu)$ and ${\cal
M}^{\prime}={\cal M}_{j}(q^{\prime},t^{\prime};\mu^{\prime})$ be maps as in
the statement, for some $i,j\in\\{0,1,2\\}$. Suppose that the map ${\cal M}$
is isomorphic to the map ${\cal M}^{\prime}$. Then, their automorphism groups
have the same order, so that $q(q-1)t=q^{\prime}(q^{\prime}-1)t^{\prime}$, and
they have the same valency, that is, $(q-1)t=(q^{\prime}-1)t^{\prime}$; the
two equalities imply that $q=q^{\prime}$ and hence $t=t^{\prime}$. It follows
that the quotients of the two maps obtained by factoring out the central
cyclic subgroup of order $t=t^{\prime}$ are also isomorphic. But these
quotients are orientably-regular embeddings of a (simple) complete graph
$K_{q}$, and by [11] their isomorphism is equivalent to $\mu=\mu^{\prime}$.

To finish the proof it remains to distinguish, for a fixed triple $(q,t,\mu)$
with even $q>4$, between the maps ${\cal M}_{0}(q,t;\mu)$ and ${\cal
M}_{1}(q,t;\mu)$. For $i\in\\{0,1\\}$ let $G_{i}={\rm Aut}^{+}{\cal
M}_{i}(q,t;\mu)=\langle x_{i},y_{i}\rangle$ be the corresponding groups, with
presentations (17) – (20) obtained by substituting $x_{i}$ and $y_{i}$ for $x$
and $y$. By [13], the two maps are isomorphic if and only if the assignment
$(x_{0},y_{0})\mapsto(x_{1},y_{1})$ extends to a group isomorphism $G_{1}\to
G_{2}$. This, however, is excluded by the relator $x^{\ell}y^{(1-q)a}$ in (20)
and the distinct values of $a=-1+it/2$ for $i\in\\{0,1\\}$.

The claim about the number of such embeddings follows immediately from Theorem
3 and the known number of distinct monic primitive polynomials over $F_{q}$.
$\Box$

Types $\\{m,n\\}$ of the maps from Theorem 4 are given by $m={\rm ord}(x)$ and
$n={\rm ord}(y)$ for $G=\langle x,y\rangle$ as in (17) – (20). We had
$n=(q-1)t$ throughout, and $m$ will now be determined from the relation
$x^{\ell}=y^{(q-1)a}$, implied by (18). The key is to observe that, taking the
quotient of $G/N\cong{\rm AGL}(1,q)$ by the central subgroup $N=\langle
y^{q-1}\rangle$ gives ${\rm ord}(Nx)=\ell$, so that $\ell$ is the smallest
positive integer such that $x^{\ell}\in\langle y^{q-1}\rangle$. It follows
that ${\rm ord}(x)$ is equal to $\ell$ times the order of $y^{q-1}$ in
$\langle y\rangle$, that is, ${\rm ord}(x)=\ell t/\gcd(a,t)$. Working out the
values of $\gcd(a,t)$ for the values of $q$, $a$ and $t$ from Theorem 3 gives
the following table of types of orientably-regular embeddings of $K_{q}^{(t)}$
for $q>4$:

Prime power | Multiplicity | Value of $a$ | Map | Type
---|---|---|---|---
$q=2^{k}>4$ | every $t\geq 1$ | $-1$ |  ${\cal M}_{0}(q,t;\mu)$ | $\\{(q-1)t,\,(q-1)t\\}$
$q=2^{k}>4$ |  $t\equiv 0$ mod $4$ | $t/2{-}1$ |  ${\cal M}_{1}(q,t;\mu)$ | $\\{(q-1)t,\,(q-1)t\\}$
$q=2^{k}>4$ |  $t\equiv 2$ mod $4$ | $t/2{-}1$ |  ${\cal M}_{1}(q,t;\mu)$ | $\\{(q-1)t/2,\,(q-1)t\\}$
$q\equiv 1$ mod $4$ | odd $t\geq 1$ | $-1$ |  ${\cal M}_{2}(q,t;\mu)$ | $\\{(q-1)t,\,(q-1)t\\}$
$q\equiv 3$ mod $4$ | odd $t\geq 1$ | $(t{-}1)/2$ |  ${\cal M}_{2}(q,t;\mu)$ | $\\{(q-1)t/2,\,(q-1)t\\}$
Table 1: Types of $t$-inflations of complete orientably-regular maps for
$q>4$.

The genus $g$ of an orientably-regular map ${\cal M}$ of type $\\{m,n\\}$ with
$G={\rm Aut}^{+}{\cal M}$ is given by Euler’s formula. Our maps have $|G|/m$
vertices, $|G|/2$ edges and $|G|/n$ faces, so that the formula reads
$|G|/m-|G|/2+|G|/n=2-2g$. For maps in Table 1, by evaluating the genus for
$|G|=q(q-1)t$ one obtains $g=1-q+q(q-1)t/4$ for type ${m,n}$ with
$m=n=(q-1)t$, and $g=1-3q/2+q(q-1)t/4$ for type $\\{m,n\\}$ where $m=(q-1)t/2$
and $n=(q-1)t$.

##  6 The three smallest prime powers

For the cases $q\in\\{2,3,4\\}$ avoided so far one could simply reproduce
available results. Our aim, however, is to re-prove them by applying the
method of ‘lifting presentations’ and show how the associated irregularities
can be overcome.

The case $q=2$ represents a singularity not only by its bipartite underlying
graphs on $2$ vertices with $t$ parallel edges (a $t$-dipole) but also by face
length $\ell=q=2$ for $K_{2}$ on a sphere. Orientably-regular embeddings of
$t$-dipoles have been classified in [6] and later in [16], but the results
follow easily also from our approach outlined in section 3. Indeed, by the
general form (2) of the lift of a presentation, orientably-regular embeddings
of $t$-dipoles are in a one-to-one correspondence with group presentations of
the form

$G_{2,t}=\langle\,x,y\ |\ x^{m},\,y^{t},\,(xy)^{2},\,x^{2}y^{f+1}\rangle\ \
{\rm with}\ \ f^{2}\equiv 1\ {\rm mod\ }t$ (22)

where $m=2t/\gcd(f+1,t)$ is the face length, and hence in a one-to-one
correspondence with solutions $f$ mod $t$ of the congruence $f^{2}\equiv 1$
mod $t$. The number of solutions of this congruence (and so the number of
orientably-regular embeddings of a $t$-dipole) is known to be $2^{r+s}$, where
$r$ is the number of distinct odd prime factors of $t$ and $s=2,\,1$ or $0$
depending on whether $t$ is divisible by $8$, by $4$ but not by $8$, and not
divisible by $4$, respectively; the genus of the embedding for such an $f$ mod
$t$ evaluates to $(t-\gcd(f{+}1,t))/2$.

The value $q=3$ is exceptional because of the face length $\ell=q=3$ for a
triangle on a sphere. Orientably-regular embeddings of $K_{3}^{(t)}$ have been
classified in [6], and later also in [9] as part of a study of inflations of
embedded cycles. The result easily follows by replacing $\ell$ with $3$ in
Step 2 of the proof of Theorem 3, giving $a=(t-3)/2$ for $q=3$. It follows
that orientably-regular embeddings of $K_{3}^{(t)}$ are in a one-to-one
correspondence with presentations $\langle\,x,y\ |\
x^{m}=y^{n}=(xy)^{2}=[x,y^{2}]=x^{3}y^{3-t}=1\,\rangle$ for $t$, $m$ and $n$
(and genus) as in Table 2, with a unique embedding for every odd $t\geq 1$.

Multiplicity | Type $\\{m,n\\}$ | Genus
---|---|---
$t$ odd, $3\mid t$ | $\\{t,2t\\}$ | $(3t-7)/2$
$t$ odd, $3\nmid t$ | $\\{3t,2t\\}$ | $(3t-3)/2$
Table 2: Orientably-regular embeddings of $K_{3}^{(t)}$.

Finally, let $q=4$, a case solved in [6] as well; it stands out by allowing a
non-trivial Schur multiplier in Proposition 1. We begin by simplifying the
presentation (17) – (20) of the group $G=G_{q,t}$ for $q=4$, observing first
that for $p=k=2$, $y_{q}=1$ and $\ell=q-1=3$ the relator in (18) containing
$b$ is immaterial. As the only primitive polynomial for $q=4$ is
$\lambda^{2}+\lambda+1$, one has $W(x,y;\mu)=y^{2}(xy)y^{-2}\cdot
y(xy)y^{-1}\cdot(xy)=y^{2}x^{3}y$, and using $x^{3}=y^{3a}$ gives
$W(x,y;\mu)y^{-3c}=y^{3(1+a-c)}$. Since the order of $y$ is the valency of the
associated orientably-regular embedding of $K_{4}^{(t)}$, equal to
$(q-1)t=3t$, we assume that ${\rm ord}(y)=3t$ in (17), so that the relator
$y^{3(1+a-c)}$ may be replaced by the condition $c=a+1$ mod $t$. Presentation
of $G$ then simplifies as follows, with $e_{1}$ replaced by $e$ for $k=2$ in
(19):

$G=G_{4,t}=\langle x,y\ |\
x^{3}y^{-3a},\,y^{3t},\,(xy)^{2},\,[x,y^{3}],[xy,yx]y^{-3e}\rangle$ (23)

We are now in position to clarify the situation for $q=4$, including an
explanation of connections of this case with the Schur multiplier from
Propositions 1 and 2.

###### Proposition 3

Let $G=\langle x,y\rangle$ be a group presented as in (23), with $y$ of order
$3t$, $t\geq 1$. If $|G|=12t$, then the parameters $a$ and $e$ mod $t$ in (23)
satisfy ${\rm(A)}$ or ${\rm(B)}$ below:

(A) $a=-1$ for arbitrary $t$, together with $a=-1+t/2$ for every even $t$; in
both cases $e=0$, $G^{\prime}=\langle[x^{-1},y],\,[y^{-1},x]\rangle\cong
C_{2}\times C_{2}$ and $G^{\prime}\cap\langle y\rangle=1$;

(B) $(a,e)=(-1\pm t/4,t/2)$ for every $t\equiv 0$ mod $4$, and
$G^{\prime}=\langle[x^{-1},y],\,[x,y],\,[y^{-1},x]\rangle$ is isomorphic to
the quaternion group in both cases, with $G^{\prime}\cap\langle
y\rangle=\langle y^{3t/2}\rangle$.

Conversely, if $G$ is a group with presentation (23) in which $t$, $a$ and $e$
satisfy $(A)$ or $(B)$, then $G$ has order $12t$. Moreover, the corresponding
orientably-regular embeddings of $K_{4}$ with edge-multiplicity $t$ are
mutually non-isomorphic, and their number is $1$, $2$, and $4$, depending on
whether $t$ is odd, $t\equiv 2$ mod $4$, and $t\equiv 0$ mod $4$,
respectively.

Proof. Let $G$ be as in the statement. Abelianisation of the presentation
(23), with $x_{\rm o}=G^{\prime}x$ and $y_{\rm o}=G^{\prime}y$, gives
$G/G^{\prime}=\langle x_{\rm o},\,y_{\rm o}\ |\ x_{\rm o}^{3}y_{\rm
o}^{-3a},\,y_{\rm o}^{3t},\,x_{\rm o}^{2}y_{\rm o}^{2},\,y_{\rm
o}^{-3e}\rangle$. Proposition 1 implies that the intersection
$G^{\prime}\cap\langle y^{3}\rangle$ has order at most $2$, and in case of
equality one has $G^{\prime}\cap\langle y^{3}\rangle=\langle y^{3t/2}\rangle$
for even $t$, as $y^{3t/2}$ is then the only involution in $\langle
y\rangle\cong C_{3t}$. It follows that the order of $y_{\rm o}$ is divisible
by $3t/2$. Comparing the values of $x_{\rm o}^{6}$ obtained by squaring the
first relator and cubing the third relator of the presentation of
$G/G^{\prime}$ gives $y_{\rm o}^{6a}=y_{\rm o}^{-6}$, which implies that
$3t/2$ divides $6(a+1)$ and hence $t\mid 4(a+1)$. This gives four values of
$a$ mod $t$: $a=-1$ for any $t$, $a=-1+t/2$ for $t$ even, and $a=-1\pm t/4$
for $t\equiv 0$ mod $4$. Before beginning to consider cases, observe that
centrality of both $x^{3}$ and $y^{3}$ from (23) together with $(xy)^{2}=1$
imply that $(x^{3}y^{3})^{2}=[xy,yx]$, independently of the value of $a$.

Let $a\in\\{-1,-1+t/2\\}$, that is, let $a=-1+\varepsilon t/2$ for
$\varepsilon\in\\{0,1\\}$; the first relator of (23) then gives
$(x^{3}y^{3})^{2}=1$. This means that also $[xy,yx]=1$, so that $y^{3e}=1$ in
(23), and by ${\rm ord}(y)=3t$ one has $e=0$. Further, from $y^{3\varepsilon
t/2}=y^{3(a+1)}=x^{3}y^{3}=x\cdot[x^{-1},y]\cdot y$ one has
$[x^{-1},y]=yxy^{3\varepsilon t/2}$ and, similarly,
$[y^{-1},x]=xyy^{3\varepsilon t/2}$.

The relation $x^{3}y^{3}=y^{3\varepsilon t/3}$ is equivalent to
$y(yxy^{3\varepsilon t/2})y^{-1}=(yx)(xy)$. The latter with
$y(xyy^{3\varepsilon t/2})y^{-1}=yxy^{3\varepsilon t/2}$ implies that
$G_{0}=\langle xyy^{3\varepsilon t/2},yxy^{3\varepsilon
t/2}\rangle=\langle[x^{-1},y],\,[y^{-1},x]\rangle$ is a normal subgroup of
$G$, isomorphic to $C_{2}\times C_{2}$. Since $G=\langle x,y\rangle$, one has
$G=G_{0}\rtimes\langle y\rangle$, and it can be checked that $G_{0}\cap\langle
y\rangle=1$, so that $|G|=12t$. But the semidirect product structure of $G$
also implies that $G^{\prime}=G_{0}$, with $G^{\prime}\cap\langle y\rangle=1$.
This proves (A).

To deal with (B), let us substitute $a=-1\pm t/4$ in the first relator of the
presentation (23) of the original group $G$; this results in
$x^{3}y^{3}=y^{\pm 3t/4}$ and $(x^{3}y^{3})^{2}=y^{3t/2}$. But we saw earlier
that $(x^{3}y^{3})^{2}=[xy,yx]$, which now implies that $y^{3t/2}\in
G^{\prime}$. Since ${\rm ord}(y)=3t$ in $G$, the commutator $[xy,yx]$ is not
trivial, and so comparison of the relations $(x^{3}y^{3})^{2}=y^{3t/2}$ and
$[xy,yx]=y^{3e}$ gives $e=t/2$ mod $t$. It may be checked that in this case
the relator containing $e$ is a consequence of the remaining ones in (23).

Centrality of $x^{3}$ and $y^{3}$ with $(xy)^{2}=1$ also imply that
$(x^{3}y^{3})^{2}=(x^{2}y^{2})^{2}=[x^{-1},y]^{2}$, so that now one has
$y^{3t/2}=(x^{3}y^{3})^{2}=[x^{-1},y]^{2}$. It follows that the commutator
$[x^{-1},y]$ has order $4$ in $G$, and one may show in a similar way that the
commutators $[x,y]$ and $[y^{-1},x]$ have order $4$ as well. But the product
of the last three commutators (in their order of appearance) is easily
verified to be equal to the involution $y^{3t/2}$, implying that in this
exceptional case $G^{\prime}$ is isomorphic to the quaternion group. This
establishes (B).

Existence of groups $G$ of order $12t$ with presentation (23) and satisfying
(A), (B) and the claim about their numbers can be shown as in the proofs of
Theorems 3 and 4. $\Box$

Types $\\{m,n\\}$ of the orientably-regular embeddings of the graphs
$K_{4}^{(t)}$ for $q=4$ are determined by the same method that was used to set
up Table 1. Here we just give a summary, including genera of the maps as a
consequence of Euler’s formula:

Multiplicity | Value of $a$ | Type | Genus
---|---|---|---
any $t\geq 1$ | $-1$ | $\\{3t,3t\\}$ | $3t-3$
$t\equiv 0$ mod $4$ | $t/2-1$ | $\\{3t,3t\\}$ | $3t-3$
$t\equiv 0$ mod $8$ | $t/4-1$ | $\\{3t,3t\\}$ | $3t-3$
$t\equiv 0$ mod $8$ | $3t/4-1$ | $\\{3t,3t\\}$ | $3t-3$
$t\equiv 2$ mod $4$ | $t/2-1$ | $\\{3t/2,3t\\}$ | $3t-5$
$t\equiv 12$ mod $16$ | $t/4-1$ | $\\{3t/2,3t\\}$ | $3t-5$
$t\equiv 4$ mod $16$ | $3t/4-1$ | $\\{3t/2,3t\\}$ | $3t-5$
$t\equiv 4$ mod $16$ | $t/4-1$ | $\\{3t/4,3t\\}$ | $3t-9$
$t\equiv 12$ mod $16$ | $3t/4-1$ | $\\{3t/4,3t\\}$ | $3t-9$
Table 3: Orientably-regular embeddings of $K_{4}^{(t)}$.

##  7 Concluding remarks: chirality, duality,
rotational powers, and Cayley maps

To wrap up, we will briefly discuss the items listed in the title of this
section, with motivation generated by their consideration in the original
paper [11].

By the general theory of maps [13], an orientably-regular map ${\cal M}$ of
type $\\{m,n\\}$ with orientation-preserving automorphism group $G={\rm
Aut}^{+}{\cal M}=\langle x,y\ |\ x^{m},y^{n},(xy)^{2},\ldots\rangle$ is
reflexible (isomorphic to its ‘mirror image’) if and only if the group admits
an automorphism inverting both $x$ and $y$; in the opposite case the map is
chiral. Similarly, a map ${\cal M}$ as above is self-dual if and only if its
group $G={\rm Aut}^{+}{\cal M}$ admits an automorphism that mutually
interchanges the generators $x$ and $y$. We will begin with chirality and
self-duality, deferring rotational powers and Cayley maps to the second part
of our concluding remarks.

Chirality. The situation for orientably-regular embeddings of the graphs
$K_{q}^{(t)}$ essentially copies the behaviour for simple complete maps from
[11], where it was also pointed out that chiral pairs correspond to pairs of
mutually reciprocal primitive polynomials.

###### Proposition 4

For $q\in\\{2,4\\}$ and any $t\geq 1$, and also for $q=3$ and any odd $t\geq
1$, all orientably-regular embeddings of $K_{q}^{(t)}$ are reflexible. For any
even $q\geq 8$ and any $t\geq 1$, and for any odd $q\geq 5$ and odd $t\geq 1$,
all orientably-regular embeddings of $K_{q}^{(t)}$ are chiral.

Proof. With $G={\rm Aut}^{+}{\cal M}=\langle x,y\rangle$ as above, it may be
checked for $q\in\\{2,3,4\\}$ and all admissible values of $t$ the
presentations of $G$ from (23) and (17) – (20) are preserved by inverting $x$
and $y$, so that this inversion extends to an automorphism of $G$ and
establishes reflexibility of the maps. For $q\geq 5$ and all admissible $t$,
suppose that one of the orientably-regular maps from Theorem 3 or Proposition
3 was reflexible, that is, that there was an automorphism $\theta$ of $G$
inverting both $x$ and $y$. Since the central subgroup $N=\langle
y^{q-1}\rangle$ would be preserved by $\theta$, the automorphism would project
onto $G/N\cong{\rm AGL}(1,q)$ and still invert the corresponding generators.
This would mean that for $q\geq 5$ the regular embeddings of simple complete
graphs of order $q$ were reflexible, contrary to the findings of [11]. $\Box$

Self-duality. As it turns out, self-duality of orientably-regular embeddings
of complete multigraphs behaves differently from [11] only for $q\leq 4$.

###### Proposition 5

An orientably-regular embedding of $K_{q}^{(t)}$ is self-dual if and only if
the prime power $q$ and multiplicity $t$ satisfy one of the following
conditions:

(i)  $q=2$, and, in (22), either $t\equiv 0$ mod $2$ and $f=1$, or $t\equiv 0$
mod $8$ and $f=1+t/2$;

(ii)  $q=4$, and, in (23), either $a=-1$ and $t\geq 1$, or $a=-1+t/2$ and
$t\equiv 0$ mod $4$, or else $a=-1\pm t/4$ and $t\equiv 8$ mod $16$;

(iii) $q\in\\{5,9\\}$ and $t\equiv 1$ mod $2$.

Proof. A necessary condition for a map of type $\\{m,n\\}$ to be self-dual is
$m=n$; this will be observed throughout in what follows, considering
$q\in\\{2,4\\}$ first (note that $m\neq n$ for $q=3$) and then developing an
argument for arbitrary $q>4$.

For $q=2$, a map corresponding to a presentation (22) can only be self-dual if
$t=m=2t/\gcd(f+1,t)$, which happens only if $f=1$ (for arbitrary even $t\geq
2$) or if $f=1+t/2$ (and then $t$ must be a multiple of $4$). In the first
case, (22) reduces to $\langle x,y\ |\
x^{t},\,y^{t},\,(xy)^{2},x^{2}y^{2}\rangle\cong C_{t}\times C_{2}$, which is
clearly invariant under the interchange of $x$ and $y$. In the second case the
presentation can be given the form $\langle x,y\ |\
x^{t},\,y^{t},\,(xy)^{2},x^{2}y^{2-t/2}\rangle$. Raising the relation
$x^{2}=y^{t/2-2}$ to the power of $(t/4{-}1)$ gives $x^{t/2-2}=y^{2}$ if
$8\mid t$ and $x^{t/2-2}=y^{t/2+2}$ if $t\equiv 4$ mod $8$. One thus has
invariance under the interchange of $x$ and $y$ if $t\equiv 0$ mod $8$, but
not if $t\equiv 4$ mod $8$, in which case invariance would require the right-
hand side of the last equation to be equal to $y^{2}$, contrary to the assumed
order of $y$. This proves (i).

If $q=4$, the situation when $m=n$ refers to the presentation (23) in which
values of $a$ and $t$ come from the first four lines of Table 3 (and with $e$
as in Proposition 3). If $a=-1$ and $e=0$, then (23) is trivially invariant
under the interchange of $x$ and $y$. If $a=-1+t/2$ for $t\equiv 0$ mod $4$,
then raising the relator $x^{3}y^{3(1-t/2)}$ to the power of $(1{-}t/2)$ gives
$y^{3}x^{3(1-t/2)}$ and hence implies the same invariance. Let now $a=-1+t/4$
and $t\equiv 0$ mod $8$; by a remark towards the end of the proof of
Proposition 3 the relator containing $e=t/2$ can be ignored. If $t\equiv 8$
mod $16$, then raising the relator $x^{3}y^{3(1-t/4)}$ to the power of
$(1{-}t/4)$ implies that $y^{3}x^{3(1-t/4)}$ and hence the above invariance.
But if $t\equiv 0$ mod $16$, the same operation results in
$x^{3(1-t/4)}y^{3(1-t/2)}$. In this case, if the presentation (23) was
invariant under interchange of $x$ and $y$, then there would also be the
relator $y^{3}x^{3(1-t/4)}$ obtained from the one we begun with. But the last
two relators imply $y^{3t/2}=1$, a contradiction. The argument for $a=-1-t/4$
is entirely similar; this shows validity of (ii).

For $q>4$ we examine effects of pairs $(\ell,a)$ from Theorem 3 on the relator
$R=x^{\ell}y^{(1-q)a}$ in the presentation (17) – (20) of $G=\langle
x,y\rangle$ in the cases when valency and face length are the same, as
displayed in lines 1, 2 and 4 of Table 1. The first and the fourth line of the
table correspond to $(\ell,a)=(q-1,-1)$ for every even $q\geq 8$ and every
$t\geq 1$, and also for every odd $q\equiv 1$ mod $4$ and odd $t$. The relator
$R$ then becomes $x^{q-1}y^{q-1}$, which implies that the cental subgroup
$N=\langle y^{q-1}\rangle<G$ is equal to $\langle x^{q-1}\rangle$. For the
pair $(\ell,a)=(q-1,t/2-1)$ for even $q\geq 8$ and $t\equiv 0$ mod $4$ from
the third line of Table 1 the relator $R$ gives $x^{q-1}=y^{(q-1)(-1+t/2)}$.
Since $4\mid t$, raising this relation to the power of $(t/2{-}1)$ gives
$x^{(q-1)(-1+t/2)}=y^{q-1}$, implying again that $N=\langle x^{q-1}\rangle$.

Suppose now that an orientably-regular embedding ${\cal M}$ of $K_{q}^{(t)}$
for some $q>4$ and $t\geq 1$ was self-dual. This would mean that its group
$G={\rm Aut}^{+}{\cal M}=\langle x,y\rangle$ from Theorem 3 and $q,t$ as in
lines 1,2 and 4 of Table 1 would admit an automorphism $\theta$ interchanging
$x$ and $y$. But the arguments in the previous paragraph show that in all such
cases the central subgroup $N$ satisfies $N=\langle y^{q-1}\rangle=\langle
x^{q-1}\rangle$, that is, $N$ is $\theta$-invariant. It follows that $\theta$
projects on to an automorphism of $G/N$ interchanging the generators $Nx$ and
$Ny$, implying that the corresponding orientably-regular embeddings of simple
complete graphs are self-dual. By [11], however, for $q>4$ this is the case if
and only if $q\in\\{5,9\\}$.

It remains to show (iii). For $q\in\\{5,9\\}$ let $\mu$ be a corresponding
primitive polynomial; there are two choices for each $q$. Invoking Theorem 4
and the notation therein but omitting subscripts, for such a pair $(q,\mu)$
and arbitrary odd $t\geq 1$ there is a unique orientably-regular map ${\cal
M}(q,t;\mu)$ arising as a $t$-inflation of an orientably-regular embedding
${\cal M}(q,1;\mu)$ of a simple complete graph $K_{q}$, in which $t=1$. For
fixed $q\in\\{5,9\\}$, presentations (13) – (15) of the groups
$G_{q;\,\mu}=G_{q;\,\mu}(u,v)={\rm Aut}^{+}{\cal M}(q,1;\mu)\cong{\rm
AGL}(1,q)$ differ only in the last relator (15) that depends on $\mu$. By
Proposition 2, for every odd $t\geq 1$ the group
$G_{q,t;\,\mu}=G_{q,t;\,\mu}(x,y)={\rm Aut}^{+}{\cal M}(q,t;\,\mu)$ of the
$t$-inflated map is a central extension of $G_{q;\,\mu}$ by $C_{t}\cong\langle
y^{q-1}\rangle$. But by [11], for $q\in\\{5,9\\}$ the original groups
$G_{q;\,\mu}(u,v)$ are invariant under interchange of $u$ and $v$, that is,
$G_{q;\,\mu}(u,v)\cong G_{q;\,\mu}(v,u)$. To proceed, recall our notational
convention of section 5 by which the generators $u$ and $v$ of the original
group turn into respective generators $x$ and $y$ in the extension. With this
in mind, construction and uniqueness implied by Theorems 3 and 4 guarantee
that the central extensions $G_{q;\,\mu}(u,v)\langle
y^{q-1}\rangle=G_{q,t;\,\mu}(x,y)$ and $G_{q;\,\mu}(v,u)\langle
x^{q-1}\rangle=G_{q,t;\,\mu}(y,x)$, obtained from each other by interchanging
$x$ and $y$ in their presentations, determine a unique central extension of
the group $G_{q;\,\mu}(u,v)\cong G_{q;\,\mu}(v,u)$. It follows that relators
in the presentation (17) – (20) determining the group $G_{q,t;\,\mu}(y,x)$
must be consequences of those obtained from its isomorphic copy
$G_{q,t;\,\mu}(x,y)$ by interchanging $x$ and $y$, and vice versa. Thus, for
odd $t\geq 1$ and $q\in\\{5,9\\}$, $t$-inflations of orientably-regular
embeddings of $K_{q}$ are self-dual. $\Box$

Rotational powers. The group $G=G(x,y)={\rm Aut}^{+}{\cal M}$ of an
orientably-regular map ${\cal M}$ can also be described in the form $G=G(y,z)$
in terms of generators $y$ and $z=xy$, the latter representing a ‘half-turn’
about the centre of an edge. For any $j$ coprime to the valency $n$ of the
map, one may form a new orientably-regular map ${\cal M}^{j}$ by replacing the
$n$-fold rotation $y$ about a vertex with its $j$-th power $y^{j}$ while
keeping $z$ intact, so that ${\rm Aut}^{+}{\cal M}^{j}=G(y^{j},z)$. Because of
the way of its creation the map ${\cal M}^{j}$ has been called the $j$-th
rotational power of ${\cal M}$ in [19], but the idea of considering a ‘$j$-th
order hole’ in maps comes from [4]; the assignment ${\cal M}\mapsto{\cal
M}^{j}$ is also known as the Wilson operator by its study in [21]. The maps
${\cal M}$ and ${\cal M}^{j}$ have the same underlying graph and abstractly
isomorphic automorphism groups, but in general they have different face length
and carrier surfaces.

By [11], for every $q\geq 2$ any two orientably-regular embeddings of $K_{q}$
can be obtained from each other by some rotational power. We first briefly
indicate a way to extend this to $t$-inflations of such maps for every $q>2$
and every odd $t>1$. Let us begin by observing that for every $j$ with
$\gcd(j,q-1)=1$ the number $j+(q-1)\tau$ is prime for infinitely many non-
negative integers $\tau$, by Dirichlet’s theorem. It follows that for every
$t>1$ there is a $\tau\in\\{0,1,\ldots,t-1\\}$ such that
$\gcd(j+(q-1)\tau,(q-1)t)=1$. Let now ${\cal M}^{(t)}$ be a $t$-inflation of
an orientably-regular embedding ${\cal M}$ of $K_{q}$ for $q>2$ and odd $t>1$.
Using the description of $t$-inflations in Theorem 3 for $q>4$ and in section
6 for $q\in\\{3,4\\}$, one may check that the uniquely determined
$(j+(q-1)\tau)$-th rotational power of ${\cal M}^{(t)}$ is isomorphic to the
unique $t$-inflation of ${\cal M}^{j}$. Theorem 4 together with the
aforementioned result of [11] on rotational powers then imply that, for every
$q>2$ and every odd $t>1$, orientably-regular embeddings of $K_{q}^{(t)}$ form
a single orbit under the Wilson operator.

The ‘unique lifting’ property may also be used for even $q\geq 8$ and even
$t\geq 2$, to be outlined next. For such $q$ and $t$ the key is to use
factorisation of the automorphism group by the central subgroup $\langle
y^{2(q-1)}\rangle$, that is, by ‘half’ of $N=\langle y^{q-1}\rangle$ used
throughout. By Theorem 4, for $t=2$ and $q=2^{k}$ with $k\geq 3$ this results
in $2\varphi(q-1)/k$ pairwise non-isomorphic maps ${\cal M}_{c}(q,2;\mu)$,
distinguished by a choice of one of the $\varphi(q-1)/k$ primitive polynomials
$\mu$ and a choice of the value of the parameter $c\in\\{0,1\\}$ from part
(II) of Theorem 3; each such maps lifts to a unique map ${\cal
M}_{c}(q,t;\mu)$. In terms of $y$ and $z$, presentations (17) – (20) of the
groups ${\rm Aut}^{+}{\cal M}_{c}(q,2;\mu)$ for $t=2$, $a=c-1$, $1\leq i\leq
k-1$, and with $W(y,z;\mu)$ obtained from $W(x,y;\mu)$ by letting $x=zy^{-1}$,
reduce to

$\langle y,\,z\ |\
y^{2(q-1)},z^{2},(yz)^{q-1}y^{(c-1)(q-1)},[y^{q-1},z],\ldots,[z,y^{i}zy^{-i}],\ldots,W(y,z;\mu)y^{(1{-}q)c}\rangle$
(24)

Let $j$ be an integer coprime to $2(q-1)$, or, equivalently, and odd integer
coprime to $q-1$. By the background on rotational powers, for $c\in\\{0,1\\}$
the automorphism group of a $j$-th rotational power of one of the maps ${\cal
M}_{c}(q,2;\mu)$ is obtained by substituting $y^{j}$ for $y$ in the
presentation (24). We will focus on the effect of such a substitution in the
third relator of (24) by evaluating $(y^{j}z)^{q-1}$ in terms of $(yz)^{q-1}$.
To do so we will use the commutation relators $[z,y^{i}zy^{-i}]$ which, by a
remark in the last paragraph of the proof of Theorem 2 and by $y^{q-1}$
commuting with $z$, extend to relators
$[y^{i^{\prime}}zy^{-i^{\prime}},y^{i}zy^{-i}]$ for any integers
$i,i^{\prime}$. Letting $z_{i}=y^{i}zy^{-i}$ for arbitrary $i$, one has
$(y^{j}z)^{q-1}=z_{j}z_{2j}\dots z_{(q-1)j}y^{(q-1)j}$. But the sets
$\\{j,\,2j,\,\ldots,\,(q-1)j\\}$ mod $q-1$ and $\\{0,\,1,\,2,\,\ldots,q-2\\}$
mod $q-1$ are identical, and note that $z_{i+i^{\prime}(q-1)}=z_{i}$ for any
$i,i^{\prime}$. Now, since any two of the $q$ terms on the right-hand-side of
the last product commute and $y^{(q-1)j}=y^{q-1}$ by oddness of $j$ and ${\rm
ord}(y)=2(q-1)$, we may rewrite the product in the form

$(y^{j}z)^{q-1}=z_{j}z_{2j}\dots z_{(q-1)j}\cdot y^{(q-1)j}=zz_{1}z_{2}\ldots
z_{q-2}\cdot y^{q-1}=(zy)^{q-1}$

and hence $(y^{j}z)^{q-1}=(zy)^{q-1}$. In view of the form of the third
relator in (24) this implies that any rotational power of a map of the form
${\cal M}_{c}(q,2;\mu)$ results in a map with the same value of $c$. Combined
with the findings of [11] for even $q>4$ it follows that for $t=2$ and any
fixed even $q>4$ there are two orbits of orientably-regular embeddings of
$K_{q}^{(2)}$ under rotational powers, one for each $c\in\\{0,1\\}$. Applying
the unique lifting described before for odd $t$ and arbitrary $q>2$ it follows
that, for every fixed even $q>4$ and even $t\geq 2$, orientably-regular
embeddings of $K_{q}^{(t)}$ form two orbits under the Wilson operator.

One may check that the conclusion from the previous paragraph is valid also
for $q=4$ and $t\equiv 2$ mod $4$. The case $q=4$ and $4\mid t$ forms an
exception again and can be resolved using factorisation by the central
subgroup $\langle y^{4(q-1)}\rangle$. This results in three orbits of regular
embeddings of $K_{4}^{(4)}$ for $q=t=4$: a singleton orbit for each
$a\in\\{-1,1\\}$ from part (A) of Proposition 3, and one orbit with two maps
for $a\in\\{0,-2\\}$ from part (B) of Proposition 3, arising from each other
by taking the $5$th and also the $7$th rotational power. The rest follows by
unique lifting as in the two cases considered above, giving one orbit for each
$a\in\\{-1,-1+t/2\\}$ and a third orbit fusing the maps for $a=-1\pm t/4$ by
$j$-th rotational powers for any $j\equiv 5$ or $7$ mod $12$ such that
$\gcd(j,3t)=1$. Summing up, one obtains:

###### Proposition 6

For every $q>2$ and $t\geq 1$, under the Wilson operator the orientably-
regular embeddings of $K_{q}^{(t)}$ form

(a) a single orbit if $t$ is odd;

(b) two orbits if both $q$ and $t$ are even and $q>4$, or if $q=4$ and
$t\equiv 2$ mod $4$;

(c) three orbits if $q=4$ and $t\equiv 0$ mod $4$. $\Box$

For completeness we note that, for $q=2$ and every $t\geq 2$, every
orientably-regular embedding of $K_{2}^{(t)}$ forms a singleton orbit under
the Wilson operator.

Cayley maps. We conclude by outlining another way of approaching inflations of
embeddings of complete graphs $K_{q}$ for prime powers $q=p^{k}$, based on
structural results of the seminal paper [11]. These imply that every
orientably-regular embedding ${\cal M}$ of $K_{q}$ has the property that the
commutator subgroup $G^{\prime}\cong C_{p}^{k}\cong F_{q}^{+}$ of the group
$G={\rm Aut}^{+}{\cal M}\cong{\rm AGL}(1,q)\cong F_{q}^{+}\rtimes
F_{q}^{\times}$ acts regularly on the vertex set of the embedded complete
graph. This not only means that one can identify the vertex set of ${\cal M}$
with $F_{q}^{+}$ via this regular action, which we will assume in what
follows, but also that the (say, anti-clockwise) cyclic order of neighbours of
every vertex $\nu\in F_{q}^{+}$ on the carrier surface of ${\cal M}$ has the
form $(\nu+1,\nu+\xi,\nu+\xi^{2},\ldots,\nu+\xi^{q-2})$ for some primitive
element $\xi\in F_{q}$ (cf. [11, section 5]). An orientably-regular map
admitting a regular action of a normal subgroup of its orientation-preserving
automorphism group on vertices has been known as a balanced Cayley map [20].
One of the outcomes of the analysis in [11] is that all the orientably-regular
embeddings of complete graphs are balanced Cayley maps.

In orientably-regular maps arising as inflations of complete maps, a regular
action of the corresponding commutator subgroup on vertices of an embedding
${\cal M}(q,t;\mu)$ of a complete multigraph $K_{q}^{(t)}$ for $q\neq 4$ is a
consequence of Proposition 2. The vertex set of ${\cal M}(q,t;\mu)$ may in
this case be identified with $F_{q}^{+}$ again, now regarded as a
$k$-dimensional vector space over $F_{p}$ formed by column vectors as in
section 4. The fact that for $t>1$ the inflated map has multiple edges turns
out to be immaterial, and for every vertex ${\mathbf{b}}\in F_{q}^{+}$ the
cyclic order of its neighbours, including their repeated occurrence, can be
described via the action $C_{(q-1)t}\cong\langle y\rangle\to{\rm
Aut}(F_{q}^{+})$, $j\mapsto A^{j}$ from Proposition 2 in the form
$({\mathbf{b}}{+}{\mathbf{e}},\,{\mathbf{b}}{+}A{\mathbf{e}},\,\ldots,{\mathbf{b}}{+}A^{j}{\mathbf{e}},\,\ldots,{\mathbf{b}}{+}A^{t(q-1)-1}{\mathbf{e}})$,
where ${\mathbf{e}}\in F_{q}^{+}{\setminus}\\{{\mathbf{0}}\\}$ is an arbitrary
but fixed vector. Thus, for $q\neq 4$, orientably-regular embeddings of
complete multigraphs on $q$ vertices are also (balanced) Cayley maps, albeit
with multiple edges. This remains valid also for $q=4$ if $G^{\prime}\cong
C_{2}\times C_{2}$ but not if $G^{\prime}$ is isomorphic to the quaternion
group. Indeed, calculations in the proof of part (B) of Proposition 3 imply
that in this case the map automorphism group contains no regular subgroup of
order $4$ on the vertex set, underscoring a remarkable exceptionality of the
situation for $q=4$ in yet another way.

We note that a general theory of Cayley maps, including those in which
underlying graphs have multiple edges, was developed in [17].

Our last remark addresses potential demand for concrete examples. Although we
did not include any, we worked out a number of particular cases in proofs of
Propositions 3 – 6. In the light of these, additional examples of substituting
concrete values of parameters in the presentation (17) – (20) are not likely
to illuminate the subject any further.

Acknowledgment. The authors acknowledge support of this research from APVV
Research Grants 19-0308 and 22-0005, and VEGA Research Grants 1/0567/22 and
1/0069/23.

## References

  * [1] D. Catalano, M. Conder, S. Du, Y. Kwon, R. Nedela and S. Wilson, Classification of regular embeddings of $n$-dimensional cubes, J. Algebraic Combin. 33 (2011), 215–238.
  * [2] M. Conder, List of orientably-regular maps of genus up to $300$, available online from https://www.math.auckland.ac.nz/$\sim$conder/
  * [3] M. Conder, J. Širáň and T. Tucker, The genera, reflexibility and simplicity of regular maps, J. Europ. Math. Soc. 12 (2010), 343–364.
  * [4] H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups, 4th Ed., Springer-Verlag, Berlin, 1984.
  * [5] S. Du and J. Zhang, A classification of orientably-regular embeddings of complete multipartite graphs, European J. Combin. 36 (2014), 437–452.
  * [6] D. Garbe, Über die regulären Zerlegungen geschlossener orientierbarer Flächen, J. Reine Angew. Math. 237 (1969), 39–55.
  * [7] A. Gardiner, R. Nedela, J. Širáň and M. Škoviera, Characterization of graphs which underlie regular maps on closed surfaces, J. London Math. Soc. 59 (1999), 100–108.
  * [8] D. Holt, What is the Schur multiplier of the affine linear group ${\rm AGL}(n,q)$? A completely worked-out answer to Question no. 191885 on mathoverflow, available at https://mathoverflow.net/questions/191885/
  * [9] K. Hu, R. Nedela, M. Škoviera and N. Wang, Regular embeddings of cycles with multiple edges revisited, Ars Math. Contemp. 8 (2015), 177–194.
  * [10] R. Jajcay, C. H. Li, J. Širáň and Y. Wang, Regular and orientably-regularmaps with quasiprimitive automorphism groups on vertices, Geom. Dedic. 203 (2019), 389–418.
  * [11] L. D. James and G. A. Jones, Regular orientable imbeddings of complete graphs, J. Combinat. Theory Ser. B 39 (1985), 353–367.
  * [12] D. L. Johnson, Presentation of Groups, LMS Student Texts 15, Cambridge Univ. Press, 2nd Ed., 1997.
  * [13] G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. (3) 37 (1978), 273–307.
  * [14] G. A. Jones, Regular embeddings of complete bipartite graphs: classification and enumeration, Proc. London Math. Soc. 101 (2010), 427–453.
  * [15] I. Miyamoto, Computation of some Cayley diagrams, Disc. Math. 72 (1988), 291–293.
  * [16] R. Nedela and M. Škoviera, Regular embeddings of canonical double coverings of graphs, J. Combinat. Theory Ser. B 67 (1996), 249–277.
  * [17] B. Richter, J. Širáň, R. Jajcay, T. Tucker and M. E. Watkins, Cayley maps, J. Combinat. Theory Ser. B 95 (2005), 189–245.
  * [18] I. Schur, Über die Darstellung der endlichen Gruppen durch gebrochene lineare Substitutionen, J. Reine Angew. Math. 127 (1904), 20–50.
  * [19] J. Širáň, How symmetric can maps on surfaces be? In: Surveys in Combinatorics, LMS Lect. Note Series 409, Cambridge University Press, 2013, 161–238.
  * [20] M. Škoviera and J. Širáň, Regular maps from Cayley graphs, Part 1: balanced Cayley maps, Discrete Math. 109 (1992), 265–276.
  * [21] S. Wilson, Operators over regular maps, Pacific J. Math. 81 (1979), 559–568.
  * [22] S. Wilson, Cantankerous maps and rotary embeddings of $K_{n}$, J. Combinat. Theory Ser. B 47 (1989), 262–273.