Skip to main content

Full text of "Automorphism Groups of Maps, Surfaces and Smarandache Geometries (Partially Post-Doctoral Research for the Chinese Academy of Sciences)"

See other formats


LINFAN MAO 


AUTOMORPHISM GROUPS OF MAPS, SURFACES 
AND SMARANDACHE GEOMETRIES 





American Research Press 
Rehoboth, NM 
2005 


Linfan MAO 


Institute of Systems Science 
Academy of Mathematics and Systems 
Chinese Academy of Sciences 
Beijing 100080, P.R.China 
maolinfan@163.com 


AUTOMORPHISM GROUPS OF MAPS, SURFACES 
AND SMARANDACHE GEOMETRIES 


Partially post-doctoral research for the Chinese Academy of Sciences 


American Research Press 
Rehoboth, NM 
2005 


This book can be ordered in a paper bound reprint from: 


Books on Demand 

ProQuest Information & Learning 
(University of Microfilm International) 
300 N.Zeeb Road 

P.O.Box 1346, Ann Arbor 

MI 48106-1346, USA 
Tel:1-800-521-0600(Customer Service) 
http: //wwwlib.umi.com/bod/search/basic 


Peer Reviewers: 

F.Tian and X.D.Hu, Academy of Mathematics and Systems, Chinese Academy of 
Sciences, Beijing 100080, P.R.China. 

Y.P.Liu and R.X.Hao, Department of Applied Mathematics, Beijing Jiaotong Uni- 
versity, Beijing 100044, P.R.China. 

S.Bhattacharya, Alaska Pacific University, AK, USA. 

H.Iseri, Department of Mathematics and Computer Information Science, Mansfield 
University, Mansfield, PA 16933, USA. 


Copyright 2005 by American Research Press and Linfan Mao 
Rehoboth, Box 141 
NM 87322, USA 


Many books can be downloaded from the following E-Library of Science: 
http://www.gallup.unm.edu/~ smarandache/eBooks-otherformats.htm 
ISBN:1-931233-92-6 


Standard Address Number: 297-5092 
Printed in the United States of America 


Preface 


A combinatorial map is a connected topological graph cellularly embedded in a 
surface. As a linking of combinatorial configuration with the classical mathematics, 
it fascinates more and more mathematician’s interesting. Its function and role in 
mathematics are widely accepted by mathematicians today. 

On the last century, many works are concentrated on the combinatorial prop- 
erties of maps. The main trend is the enumeration of maps, particularly the rooted 
maps, pioneered by W. Tutte, and today, this kind of papers are still appeared on 
the journals frequently today. All of those is surveyed in Liu’s book [33]. To deter- 
mine the embedding of a graph on surfaces, including coloring a map on surfaces 
is another trend in map theory. Its object is combinatorialization of surfaces, see 
Gross and Tucker [22], Mohar and Thomassen [53] and White [70], especially the 
[53] for detail. The construction of regular maps on surfaces, related maps with 
groups and geometry is a glimmer of the map theory with other mathematics. 

In fact, maps as a kind of the decomposition of surfaces, should be given more 
attention to its role in surfaces theory, such as the Riemann surfaces, Klein surfaces 
and manifolds theory. As a simple case of the general manifolds, we know that 
Riemann surfaces have become a source of the mathematical creative power. Many 
good ideas for the manifolds with higher dimension are inspired by the Riemann 
surfaces. The relation of maps with Riemann surfaces has been known in 80s in the 
last century. Then how to realization or making combinatorial refinement for the 
Riemann surfaces, Riemann geometry and finally, the Smarandache geometries by 
maps is a very interesting problem. Unless the enumeration of unrooted maps on 
surfaces, more attentions are given to the combinatorial refinement of some famous 
results in Riemann surfaces, Klein surfaces and s-manifolds in this book. Although 
the results obtained are quite elementary, it is still valuable probe by researchers, 
especially, those of mathematicians in combinatorics, Klein surfaces or Smarandache 
geometries. 

Now we outline the main contents in each chapter. 

Chapter 1 is preliminary. We introduce the conceptions of Klein surfaces, 


Smarandache geometries, maps and the semi-arc automorphism group of a graph. 


Preface il 


A relation for maps and Smarandache manifolds (abbreviated s-manifolds) and a 
scheme for the enumeration of unrooted maps are established in this chapter. The 
last section determines the relation of the number of embeddings and rooted maps 
of a graph on genus. A general equation for the total genus polynomial and rooted 
total map polynomial is found in this section. 

As a combinatorial model of the Klein surfaces and s-manifolds, Chapter 2 con- 
cerns the automorphisms of a map, a Klein surface and an s-manifold. The voltage 
map in the topological graph theory is defined by algebraic and some common results 
are reproved under this definition. Conditions for a group being that of a map are 
gotten in the first two sections. A combinatorial refinement of the Hurwitz theorem 
in Riemann surfaces, and similar results for the Klein surfaces and s-manifolds are 
obtained in the Section 3. The Section 4 concerns the order of an automorphism 
of Klein surfaces and s-manifolds by maps, which is an interesting problem for re- 
searchers in the Klein surfaces and Smarandache geometries. The results gotten in 
this section are better than those of results already known. 

Chapter 3 presents a necessary and sufficient condition for a group of a graph 
being that of a map. This chapter also give all concrete representation of automor- 
phisms of maps underlying a complete graph, a semi-regular graph and a bouquet, 
which is difficult in the researching of Klein surfaces. 

Chapter 4 is concentrated on the enumeration of unrooted maps and s-manifolds 
by applying the results obtained in the previous chapters. The enumeration prob- 
lem of unrooted maps on surfaces is generally recognized a difficult problem. The 
unrooted complete maps, the semi-regular maps and one face maps on orientable 
and non-orientable surfaces are enumerated in this chapter. The last section gives 
an elementary classification for the closed s-manifolds by maps. 

The last chapter presents some open problems related to the Riemann geometry 
and Smarandache geometries for the combinatorial maps. Although it is called 
open problems, in fact, any solution for one of these problems needs to establish 
a new mathematical system first. But as soon as the system has been established, 
the contribution of combinatorics to classical mathematics, such as, the Riemann 
geometry and Smarandache geometries is realized. Those are the wish of mine, and 
they are also the main problems considered by me in the following times. 


The main part of this book is my post-doctor report in the Chinese Academy 


Preface ui 


of Sciences in 2005. Many colleagues and friends of mine have given me enthusiastic 
support and endless helps in preparing this book. Without their helps, this book 
will never appears. Here I must mention some of them. On the first, I would like to 
give my sincerely thanks to Professor Feng Tian for his encouraging and invaluable 
helps and to professor Yanpei Liu introduced me into the filed of combinatorial map 
theory. Thanks are also given to Professor Mingyao Xu, Professor Yanxun Chang, 
Professor Xiaodong Hu, Professor Han Ren, Professor Rongxia Hao, Professor Weili 
He and Erling Wei for their kindly helps and often discussing problems in mathe- 
matics altogether. Of course, I am responsible for the correctness all of the material 


presented here. Any suggestions for improving this book are welcome. 


L.F.Mao 
AMSS, Beijing 
June, 2005 


Contents 


PROIACEY xcieeser get tuted matics aes Yad Ahn nti ss ae acy Seat a Gatti eat ady go bon i 
Chapter 1) Preliminary (irs o65 035 aia. 5 eeeics Sth Mache pope Rie Bet ced aes 1 
SI Wlein:-surtace and: s-miamitlolde sss aca he hes Pon ue oes eee eet Re ed 1 
Wit PVM OMS aud thet Raley ck eth SEs otek ia ee, Ghd A etek se tial ots Ree OAR ales ths 1 
1.2 Classification of Klein surfaces and s-manifolds ................. 00: e cece eee ee 3 
§2 Map and embedding of a graph on surface.............0 0. ccc eee eee eens 4 
PZ AMG TADS: Sclcke peewee ue tet hrs Merc ee eM Se Ae ate te anda 4 
2.2 The embedding of a graph on surfaces .........0...00 0 cece cece e eee 6 
2/3, ia peand: TOO led: Ina ON SUTACE ised Went ss Waele Sosa a hak Uae te aes 8 
2.4 Classification maps and embeddings of a graph on a surfaces................ 10 
2.5 Maps as a combinatorial model of Klein surfaces and s-manifolds .......... 12 


83 The semi-arc automorphism group of a graph with application to maps enumer- 


AULOM as. heer cereals a wake eg ace eyneruesh werk g meen Herts dh teat nates Gate bea tae Saeeetace 13 
3.1 The semi-arc automorphism group of a graph................00 eee eee eee 13 
3.2 A scheme for enumerating maps underlying a graph...................0.200- 1 


84 A relation among the total embeddings and rooted maps of a graph on genus 20 
4.1 The rooted total map and embedding polynomial of a graph................ 20 
4.2 The number of rooted maps underlying a graph on genus................... 24 


Chapter 2 On the automorphisms of a Klein Surface and a s-manifold 31 


§1 An algebraic definition of a voltage map............. 0. c cece ccc eee ees 31 
Tal Coverings Or a diapl Susie eine ais eh od one Reha els Maa ee es 31 
Ie Volage MAPS .s asuaccouis we neachemiees dete ad onud Ree nl ewkte aed Same nea 30 
§2 Combinatorial conditions for a group being that of amap................... 35 
2.1 Combinatorial conditions for an automorphism group of a map............. 36 
27, The M@aeures OMA: MAG aint teehee esate wits ein gteat atu enc ts ihe cata tethetc has ate a aes Al 
83 A combinatorial refinement of Huriwtz theorem ...............0 0c cece eee 44 
84 The order of an automorphism of a Klein surface...................0.00 000s 50 
4.1 The minimum genus of a fixed-free automorphism ...................0.0000- 51 


4.2 The maximum order of an automorphism of a map.................0000 000 54 


Contents Vv 


Chapter 3 On the Automorphisms of a graph on Surfaces.............. 57 
81 A necessary and sufficient condition for a group of a graph being 

GHA Ol AMA jo aide cast iptait Maeda iva nena aitaans eae Peake Gade 57 
82 The automorphisms of a complete graph on surfaces.............00..0 00 eee 64 
83 The automorphisms of a semi-regular graph on surfaces .................244. 73 
$4. ‘The:-automorphisms of one face maps «2.5. eo eva se Se eee ee eee 76 


Chapter 4 Application to the Enumeration of Unrooted Maps and s- 


ITA EON Seed 2s fin ings neu AAA et te Gece at ee ee Ret tended ae rena Ia ke 81 
§1 The enumeration of unrooted complete maps on surfaces ................0005 81 
§2 The enumeration of a semi-regular graph on surfaces ...........0...002.20 000s 88 
83 The enumeration of a bouquet on surfaces.......... 0... c cece eee eens 91 
$4 A classification ‘of the closed s-mamilolds «i044 tev dawagoason sheen kia 97 
Chapter 5 Open Problems for Combinatorial Maps .................... 103 
5.1 The uniformization theorem for simple connected Riemann surfaces........ 103 
gi2- he: Ricnigim= Och GWeOremt .<x'ca 24 cus eed eon veer ety ee dea lah we Rees 104 
5.3 Combinatorial construction of an algebraic curve of genus ................. 105 
5.4. Classification-of s-manifolds by mapsicc ii c.cscenina eon ceca ebae ts Geckos 105 
Ho aaliss Map pine AIMOne SUlACES rs «a9 Cesierndeimetcanas ee Gore ee en eee ean 106 
56 “The Gause- Bonnet (heoreim: 3/60 35.4 4 naga iad eng als eae eek piee yy 106 
oot Wiemann MantOlds sl wutcenceden tohee hares erent eer eed ekcks aotet 107 
TRETEV CHC CGY st tes wits eis Ui th Asa tle AS tc An Aa ee Od Sa TN oe da 108 


Chapter 1 Preliminary 


All surfaces are 2-dimensional compact manifolds without boundary, graphs are 
connected, possibly with loops or multiple edges and groups are finite in the context. 
For terminology and notation not defined in this book can be seen in [33], [34] and 


[35] for graphs and maps and in [6], [73] for groups. 


§1. Klein surface and s-manifold 


1.1 Definitions 


1.1.1 Definition of a Klein surface 


The notion of Klein surface is introduced by Alling and Greenleaf [2] in 1971 
concerned with real algebraic curves, correspondence with that of Riemann surface 
concerned with complex algebraic curves. For introducing this concept, it is need 
to enlarge analytic functions to those of dianalytic functions first. 

Now let f : A —> C bea mapping. Write z = x +iy,2,y € R,i = V—1,7 = 
x —iy and f(z) = u(a,y) + iv(2,y) f(z) = ulz,y) — iv(a, y)for certain functions 
u,v: A—->R. 

A mapping f : A —> C is analytic on A if of = 0 (Cauchy-Riemann equation) 
and is antianlytic on A if of =: 

A mapping f is said to be dianalytic if its restriction to every connected com- 
ponent of A is analytic or antianalytic. 

Now we can formally define a Klein surface. 

A Klein surface is a Hausdorff, connected, topological space S together with a 
family > = {(U;, ¢;) |i € I} such that the chart {U;|i € I} is an open covering of 
S, each map ¢; : U; —> A; is a homeomorphism onto an open subset A; of C or 
Ct = {z €C: Imz > 0} and the transition functions 


Pig = PiP; : 6;(Ui()U;) =e bi(Ui (Uj). 
are dianalytic. 


The family }° is said to be a topological atlas on S. 


Chapter 1 Preliminary 2 


The boundary of S is the set 


OS = {x € S|there existsicl,x €U;,¢;(47) ER 
and (Uj) CCT}. 


The existence of Klein surfaces is obvious, for example, a Riemann surface is 
a Klein surface viewed as an orientable surface with empty boundary and > to be 


analytic functions. Whence, we have the following relation: 


{Riemann Sufaces} C {Klein sur faces}. 


The upper half plane H = {z € C|\Imz > 0} with {(U, = H, ¢; = 1q)} and the 
open unit disc D = {z € C||z| < 1} with {(U, = d,¢, = 1p)} in C are two Klein 
surfaces with empty boundary and analytic structures. 

If k(S),g(S) and y(S) are the number of connected components of 0S, the 


topological genus and the Euler characteristic of a surface S, then we have that 
Theorem 1.1.1(([2]) 


(Ss) = 2 — 29(S) — k(S), if S is orientable, 
ie 2—g9(S)—k(S). if Sis non — orientable. 


1.1.2 Definition of a Smarandache geometry 


By the history, we know that classical geometries include the Euclid geom- 
etry, the hyperbolical geometry and the Riemann’s geometry. Each of the later 
two is proposed by denial the 5th postulate for parallel lines in the Euclid postu- 
lates of geometry. The Smarandache geometries is proposed by Smarandache in 
1969 ({61]), which is a generalization of the classical geometries, i.e., the Euclid, 
Lobachevshy-Bolyai-Gauss and Riemannian geometries may be united altogether in 
the same space, by some Smarandache geometries. These last geometries can be 
either partially Euclidean and partially Non-Euclidean, or Non-Euclidean. It seems 
that the Smarandache geometries are connected with the Relativity Theory (because 
they include the Riemann geometry in a subspace) and with the Parallel Universes 


(because they combine separate spaces into one space) too({32]). 


Chapter 1 Preliminary 3 


In [61], Smarandache defined several specific types of Smarandache geometries, 
such as the paradoxist geometry, the non-geometry, the counter-projective geometry 
and the anti-geometry. He also posed a question on the paradoxist geometry, i.e., 
find a nice model on manifolds for this paradoxist geometry and study some of its 
characteristics. 

An axiom is said smarandachely denied if in the same space the axiom behaves 
differently (i.e., validated and invalided; or only invalided but in at least two district 
ways). 

A Smarandache geometry is a geometry which has at least one smarandachely 
denied axiom'* . At present, the Smarandache manifolds (abbreviated s-manifolds) 
are the central object discussed in the Smarandache geometries today. More results 
for the Smarandache geometries can be seen in the references [4], |16],/27] — [28], [32] 
and [58] — [59] etc.. 

The idea of an s-manifold was based on a hyperbolic paper in [69] and credited 
to W.Thurston. A more general idea can be found in [59]. According to the survey 
[27] of H.Iseri, an s-manifold is combinatorially defined as follows: 

An s-manifold is any collection C(T,n) of these equilateral triangular disks 
T;,1<i<n satisfying the following conditions: 

(1) Each edge e is the identification of at most two edges e;,e; in two distinct 
triangular disks T;,T;,1 <i,j <n andi Fj; 

(ii) Each vertex v is the identification of one vertex in each of five, siz or seven 
distinct triangular disks. 

The vertices are classified by the number of the disks around them. A vertex 
around five, six or seven triangular disks is called an elliptic vertex, a Euclid vertex 
or a hyperbolic vertex, respectively. 

An s-manifold is called closed if the number of triangular disks is finite and each 
edge is shared by exactly two triangular disks, each vertex is completely around by 
triangular disks. It is obvious that a closed s-manifold is a surface and its Euler 


characteristic can be defined by the Theorem 1.1.1. 


1.2 Classification of Klein surfaces and s-manifolds 


A morphism between the Klein surfaces S and 5” is a continuous map f : S — S’ 


‘Also see www.gallup.unm.edu/~ samrandache/geometries.htm 


Chapter 1 Preliminary 4 


such that f(0S) C 0S’ and given s € S, there exist chart (U,@) and (V,~) at s and 
f(s) respectively, and an analytic function F' : ¢(U) —C such that 


Y(F(s)) = QF (els); 


where, ®:C > Ct: a2+iy > 2+%|y| is a continuous map. 

An automorphism of a Klein surface S$ is an 1—1 morphism f : S — S. It has 
been known that for a given Klein surface S, the set Aut.S of automorphisms of S 
forms a group with respect to the composition operation and AutH = PGL(2, R). 

Let I. be a discrete subgroup of AutH. We say that T is a non-euclidean 
crystallographic group( shortly NEC group) if the quotient H/T is compact. 

More results can be seen in [11]. Typical results for automorphisms of a Klein 


surface S are as follows. 


Theorem 1.1.2({11]) Let S be a compact Klein surface, g = g(S) and k = k(S), 
then 
(i) there exists an NEC groupT such that AutS = No(T)/T, whereQ = AutH. 
(ii) if S satisfies the condition 2g +k > 3 if S is orientable andg+k>3 if S 


is non-orientable, then AutS' is finite. 


Similarly, two s-manifolds C,;(T,n) and C2(T,n) are called to be isomorphic if 
there is an 1 — 1 mapping 7 : C)(T,n) — C2(T,n) such that for VT), T2 € Ci(T,n), 


7(Ty ()T2) = 7(T1) ()1(Tp). 
If Ci(T,n) = C\(T,n) = C(T,n), 7 is called an automorphism of the s-manifold 
C(T,n). All automorphisms of an s-manifold form a group under the composition 


operation, called the automorphism group of an s-manifold C(T,n), denoted by 
AutC(T,n). 


§2. Map and embedding of a graph on surface 


2.1 Graphs 


Combinatorially, a graph I is a 2-tuple (V, £) consists of a finite non-empty 


set V of vertices together with a set FE of unordered pairs of vertices, ie., EC 


Chapter 1 Preliminary i) 


V x V((22], [35], [70]). Often denoted by V([), E(I) the vertex set and edge set of 
the graph I. 

The cardinal numbers of |V| and |£| are called the order and the size of the 
graph T. 

We can also obtain a representation of a graph I’ representing a vertex u by a 
point p(u), p(u) £ p(v) if u A v and an edge (u,v) by a curve connecting the points 
p(u) and p(v) on the plane. 

For example, the graph in the Fig. 1.1 






3 


Fig 1.1 


is a graph T = (V, FE) with V = {u,v,w, x} and 


Bt (Uy, wy), (O20); G0), (a5), Cb 0), (Ue) Aw), (as 


A walk of a graph I is an alternating sequence of vertices and edges wy, €1, U2, €2, 
++, €n, Un, With e; = (u;,Uj41) for 1 <7 <n. The number n is the length of the 
walk. If wy = Un41, the walk is said to be closed, and open otherwise. For example, 
ue Ve2wegwe3re3wegu is a walk in the graph of the Fig. 1.1. A walk is called a trail 
if all its edges are distinct and a path if all the vertices are distinct. A closed path 
is said to be a circuit. 

A graph IT is connected if there is paths connecting any two vertices in this 
graph and is simple if any 2-tuple (u,v) € E([) C V(L) x V(L) appears once at 
most and uF v. 

Let [ be a graph. For Vu € V(I), the neighborhood N#(u) is defined by 
Ne(u) = {v|(u, v) or (v,u) € E(T)}. Its cardinal |N#(w)| is called the valency of the 


Chapter 1 Preliminary 6 


vertex u in the graph [’, denoted by pr(u). By the enumeration of edges, we know 


the following result 
dou € V(P)pr(u) = 2|E(P). 


2.2 The embedding of a graph on surfaces 


A map on a surface S is a kind of partition S which enables us to obtain 
homeomorphisms of 2-cells {(«, y)|v? + y? < 1,2,y € R} if we remove from S' all 
the curves used to partite S. There is a classical result for the partition of a surface 
gotten by T.Rado in 1925. 


Theorem 1.2.1([52]) For any compact surface S, there exist a triangulation {T;,i > 
1} on S. 


This theorem is fundamental for the topological graph theory, which enables us 
to discussion a surface combinatorially. 

For any connected graph [ = (V(T), E(()) and a surface S, an embedding of 
the graph [ in the surface S' is geometrical defined to be a continuous 1 — 1 mapping 
7:I— 8S. The image 7([) is contained in the 1-skeleton of a triangulation of the 
surface S. If each component in S — 7([.) homeomorphic to an open disk, then the 
embedding is said a 2-cell embedding, where, components in S — 7(T) are called 
faces. All embeddings considered in this book are 2-cell embeddings. 

Let I be a graph. For v € V(I), denote by Np(v) = {e1, €2,-++, pv) } all the 
edges incident with the vertex v. A permutation on €1,€2,---,€,(y) is said a pure 
rotation. All pure rotations incident a vertex v is denoted by o(v). A pure rotation 


system of the graph [ is defined to be 


A(T) = {e(v)|u Ee VT)} 


and all pure rotation systems of the graph [ is denoted by o(T). 
The first characteristic for embedding of a graph on orientable surfaces is found 
by Heffter in 1891 and formulated by Edmonds in 1962, states as follows. 


Theorem 1.2.2({17|) Every pure rotation system for a graph T induces a unique 


Chapter 1 Preliminary 7 


embedding of Tl into an orientable surface. Conversely, every embedding of a graph 


T into an orientable surface induces a unique pure rotation system of I. 


According to this theorem, we know that the number of orientable embeddings 
of a graph [ is T,eviry(p(v) — 1)!. 

The characteristic for embedding of a graph on locally orientable surface is used 
by Ringel in the 1950s and gave a formal proof by Stahl in 1978([22][62]). 

From the topological theory, embedded vertex and face can be viewed as disk, 
and an embedded edge can be viewed as an 1-band which is defined as a topological 
space B together with a homeomorphism h : I x I — B, where I = [0,1], the unit 
interval. 

Define a rotation system p”(I) to be a pair (7, A), where J is a pure rotation 
system of T, and A: E(I) > Zo. The edge with \(e) = 0 or A(e) = 1 is called type 
0 or type 1 edge, respectively. The rotation system of a graph I are defined by 


oT) ={(F, AF € off), A: BYP) > Z}. 
Then we know that 


Theorem 1.2.3({22]|62]) Every rotation system on a graphT defines a unique locally 
orientable embedding of . — S. Conversely, every embedding of a graph Tl — S 


defines a rotation system for T. 


For any embedding of the graph I’, there is a spanning tree 7’ such that every 
edge on this tree is type 0([43]). Whence the number of embeddings of a graph [ 


on locally orientable surfaces is 


2°) TT (e(v) - 2)! 


veV(T) 


and the number of embeddings of [ on the non-orientable surfaces is 


Qvale Mai! 


veV(T) 
The following result is the Euler-Poincaré formula for an embedding of a graph 


on surface. 


Theorem 1.2.4 Jf a graph T can be embedded into a surface S, then 


Chapter 1 Preliminary 8 


V(P) — e(L) + oP) = x(S), 


where, v('),e(L) and (TL) are the order, size and the number of faces of the graph 
I, and y(S) is the Euler characteristic of the surface S: 


2 — 2p, if S is orientable, 
x(S) = | 


2-—q, if Sis non — orientable. 


2.3. Map and rooted map on surface 


In 1973, Tutte gave an algebraic representation for an embedding of a graph on 
locally orientable surface ([66], which transfer a geometrical partition of a surface 
to a kind of permutation in algebra. 

According to the summary in [33], a map M = (%X,,3,P) is defined to be a 
basic permutation P, i.e, for any 7 € %,g, no integer k exists such that P*x = az, 
acting on V,,g, the disjoint union of quadricells Ka of « € X (the base set), where 


K = {1,a,3,a(} is the Klein group, satisfying the following two conditions: 

(Ci) ~P = Pa; 

(Cii) the group V7 =< a,3,P > is transitive on Xq,g. 

For a given map M = (%,,,P), it can be shown that M* = (¥3..,Pa/) is 
also a map, call it the dual of the map M. The vertices of M are defined as the 
pairs of conjugatcy orbits of P action on 4,8 by the condition (Ci) and edges the 
orbits of K on %,,8, for example,Vz € Va,8, {v, ax, Bx, aBx} is an edge of the map 


M. Define the faces of M to be the vertices in the dual map M*. Then the Euler 
characteristic y(/) of the map M is 


x(M) = v(M) — e(M) + 6(M) 


where,v(M/),¢(M), ¢(/) are the number of vertices, edges and faces of the map M, 
respectively. 
For example, the graph Ky, on the tours with one face length 4 and another 8 , 


shown in the Fig. 1.2, can be algebraic represented as follows: 


Chapter 1 Preliminary 9 


A map (Xa,2,P) with Xo6 = {2,y, 2, U,V, W, a2, ay, az, au, av, aw, Bx, By, Bz, 


Bu, Bv, Bw, aba, aBy, a8z, aBu, o8v, aw} and 


P = (2,y,2)(aGz, u, w)(aBz, aBu, v)(aBy, abv, abw) 
x (ax,az,ay)(Bx, aw, au)(Bz, av, Bu)(By, Bw, Bv) 
The four vertices of this map are {(z, y, z), (ax, az, ay)}, {(aGx, u, w), (Bx,aw,au)}, 
{(aZBz,aBu,v), (Bz, av, Bu)} and {(aBy, aBv, aBw), (By, Bw, Bv)} and six edges are 
{e, ae, Be,aBel, where, e € {x,y,z,u,v,w}. The Euler characteristic y(M) is 
x(M) =4-6+2=0. 





Fig 1.2 


Geometrically, an embedding M of a graph I on a surface is a map and has an 
algebraic representation. The graph IT is said the underlying graph of the map M 
and denoted by l = '(M). For determining a given map (%4,g,P) is orientable or 


not, the following condition is needed. 


(Citi) If the group Vr =< aZ,P > is transitive on Xq,3, then M is non- 


orientable. Otherwise, orientable. 


It can be shown that the number of orbits of the group Vy; =< af,P > in 
the Fig.1.1 action on Xo,g = {2, y, 2, U,V, W, AZ, ay, az, au, av, aw, Bx, By, Bz, Bu, 
Bu, Bw, ax, aBy, aBz, abu, aBv,abw} is 2. Whence, it is an orientable map and 
the genus of the surface is 1. Therefore, the algebraic representation is correspondent 


with its geometrical mean. 


Chapter 1 Preliminary 10 


A rooted map M* is a map M such that one quadricell x € %Xy,g is marked 
beforehand, which is introduced by Tutte in the enumeration of planar maps. The 
importance of the root is to destroy the symmetry in a map. That is the reason why 


we can enumerate rooted maps on surfaces by combinatorial approaches. 


2.4. Classification maps and embeddings of a graph on surfaces 


2.4.1 Equivalent embeddings of a graph 


From references, such as, [22],[70], etc., two embeddings (71, A1), (J2, A2) of 
I on an orientable surface S are called equivalent if there exists an orientation- 
preserving homeomorphism 7 of the surface S such that 7: J, — Jo, and TA = Ar. 
If (A%,A1) = (fo,A2) = (I,A), then an orientation-preserving homeomorphism 
mapping (%,A1) to (%2,Az2) is called an automorphism of the embedding (7, A). 
Certainly, all automorphisms of an embedding form a group, denoted by Aut(7, A). 

Enumerating the non-equivalent orientable embeddings of a complete graph 
and a complete bipartite graph are considered by Biggs, White, Mull and Rieper 
et al in [6], [54] — [55]. Their approach is generalized in the following Section 2.3.2 
for enumerating non-equivalent embeddings of a given graph on locally orientable 


surface in the view of maps on surfaces. 


2.4.2 Isomorphism of maps 


Two maps M, = (4).4,Pi1) and M; = (¥34,P2) are said to be isomorphic if 


there exists a bijection € 


1 2 
€: Xa8 — Aa,, 


such that for Vz € X24, 


a(x) = a€(x),€3(x) = B&(x) and €Pi(x) = Po€(z). 
Call € an isomorphism between M, and Mo. If M,; = My = M, then an isomorphism 
between M, and Mg is called an automorphism of M. All automorphisms of a map 
M form a group, called the automorphism group of M and denoted by AutM. 
Similarly, two rooted maps M7, M§ are said to be isomorphic if there is an 


isomorphism @ between them such that (x) = y. All automorphisms of a rooted 


Chapter 1 Preliminary 11 


map M” also form a group, denoted by AutM”. It has been known that AutM” is 
trivial ((33]). 

Using isomorphisms between maps, an alternative approach for determining 
equivalent embeddings of a graph on locally orientable surfaces can be gotten, which 
has been used in [43], [49]—[50] for determining the number of non-equivalent embed- 
dings of a complete graph, a semi-regular graph and a Cayley graph T = Cay(G: S) 
with Aut! = R(G) x H, is defined as follows. 

For a given map M underlying a graph I, it is obvious that AutM|p < Aut. 
We extend the action Vg € Autl on V(T) to Vag, where X = E(T), as follows: 

Va € Xag, if 29 =y, then define (ax)? = ay, (Gx)? = By and (afr)? = afy. 

Two maps (embeddings) MM), M2 with a given underlying graph [ are equivalent 
if there exists an isomorphism ¢ between them induced by an element €. Call ¢ an 
equivalence between M,, M2. Certainly, on an orientable surface, an equivalence 


preserve the orientation on this surface. 


Theorem 1.2.5 Let M = (%.,8,P) be a map with an underlying graphl, Vg € Autl. 
Then the extend action of g on Xq,g with X = E(T) is an automorphism of map M 
iff Yu € V(M), g preserves the cyclic order of v. 


Proof Assume that ¢ € AutM is induced by the extend action of an automor- 
phism g in I, u,v € V(M) and u2 = v. Not loss of the generality, we assume 
that 


= Gils, 2050) ) (Abaya ON) 


US (y1, Yasir, Yoru) (OU pta)s “5, QY2, ay). 


Without loss of generality , we can assume that 


(21, £2, ae sara)" = (Yi, Y2, :. esata) 


that is, 


(9(1), 9(@2), +++, 9(Zo(u))) = (Yr, Yas +s Yow): 


Whence, g preserves the cyclic order of vertices in the map M. 


Chapter 1 Preliminary 12 


On the other hand, if the extend action of g € Autl’ on .,g preserves the cyclic 
order of each vertex in M, ie., Vu € V(T),4u € V(L) such that uy = v. Assume 
that 





weV(M) 
Then 
(ea Il i = II C— PP. 
ueV(M) veV(M) 
Therefore, the extend action of g on Xy,g is an automorphism of the map M. 4 


2.5 Maps as a combinatorial model of Klein surfaces and s-manifolds 


2.5.1 The model of Klein surfaces 


Given a complex algebraic curve, it is a very important problem to determine its 
birational automorphisms. For curve C of genus g > 2, Schwarz proved that Aut(C) 
is finite in 1879 and Hurwitz proved |Aut(C)| < 84(g— 1)(see [18] ). As observed by 
Riemann, groups of birational automorphisms of complex algebraic curves are the 
same as the automorphism groups of the compact Riemann surfaces. The latter can 


be combinatorially dealt with the approach of maps. 


Theorem 1.2.6([8][29]) If M is an orientable map of genus p, then AutM is iso- 


morphic to a group of conformal transformations of a Riemann surface of genus 
D. 
According to the Theorem 1.1.2, the automorphism group of a Klein surface 


has the same form as a Riemann surface. Similar to the proof of the Theorem 5.6 


in [29], we can get a result similar to the Theorem 1.2.6 for Klein surfaces. 


Theorem 1.2.7 If M is a locally orientable map of genus q, then AutM is isomorphic 


to a group of conformal transformations of a Klein surface of genus q. 


Proof By a result in [8], AutM © Nr(A)/A, Where T =< a,b, cla®7=b? =? = 
(ba)? = (ac)™ = (cb)” = 1 >, A < T and T can be realized by an automorphism 
group of a tessellation on the upper plane, A a NEC subgroup. According to the 


Chapter 1 Preliminary 13 


Theorem 1.1.2, The underlying surface S of M has S = H/A with Q = AutH = 
PGL(2,R) being the automorphism group of the upper half plane H. Since T < Q, 
we know that Aut = N7(A)/A < No(A)/A, isomorphic to a group of conformal 
transformations of the Klein surface S = H/G. h 


2.5.2 The model of closed s-manifolds 


For a closed s-manifold C(T’,n), we can define a map M by V(M) = {the vertices in 
C(T,n)}, E(M) = {the edges in C(T,n)} and F(M) = {T,T € C(T,n)}. Then, M 
is a triangular map with vertex valency € {5,6,7}. On the other hand, if M isa 
triangular map on surface with vertex valency € {5,6,7}, we can define C(T, ¢()) 
by 


C(T, o(M)) = tflf € FU)}. 
Then, C(T, 6(M)) is an s-manifold. Therefore, we get the following result. 


Theorem 1.2.8 Let C(T,n), M(T,n) and M*(T,n) be the set of s-manifolds with 
n triangular disks, triangular maps with n faces and vertex valency € {5,6,7} and 
cubic maps of order n with face valency € {5,6,7}. Then 


oe. 


(i) There is a bijection between M(T,n) and C(T,n); 


ae 


(ii) There is also a bijection between M*(T,n) and C(T,n). 


§3. The semi-arc automorphism group of a graph with application to 


maps enumeration 


3.1 The semi-arc automorphism group of a graph 


Let [ be a graph with vertex set V(I) and edge set E(I). By the definition, 
an automorphism of T on V(T) UE(L) is an 1 — 1 mapping (€,7) on [ such that 


E:V(T) 3 V(T), 7: (1) - E(T), 


satisfying that for any incident elements e, f, (€,7)(e) and (€,7)(f) are also incident. 
Certainly, all automorphisms of a graph I form a group, denoted by AutI. 


Chapter 1 Preliminary 14 


Now an edge e = wv € E(T) can be divided into two semi-arcs ey, e,. Call u 
the root vertex in the semi-arc e,. Two semi-arc €,, f, are said incident if u = v 
or e = f. The set of all semi-arcs of a graph TI is denoted by X 1 ([). A semi-arc 
automorphism of a graph, first appeared in [43] and then applied to the enumeration 


rooted maps on surfaces underlying a graph [ in [46], is defined as follows. 


Definition 1.3.1 An 1—1 mapping € on X1(T) such that Ve, fy € Xi(T), E(€,,) 
and €(fy) are incident if e, and fy are incident, is called a semi-arc automorphism 
of the graph I. 


All semi-arc automorphisms of a graph also form a group under the composition 
operation, denoted by Aut 1 I’, which is more important for the enumeration of maps 
on surfaces underlying a graph and by the discussion of the Section 2, which is 
also important for determine the conformal transformations on a Klein surface. 
The following table lists semi-arc automorphism groups of some well-known graphs, 
which give us some useful information for the semi-arc automorphism groups, for 
example, Auti kK, = 5%) bit Aut1 Bn, = 5709] + AutB,. 


Sk, min! 
So[Sin] 2n!? 


Sn[ So] Qn! 
SoS, Qn! 
Dpk'(k £1) | S2[Sz] x Sp X So[Si] | 2*+ntkll! 
Dp®* 55% By (So[5,)) | 22 alk? 
table 3.1 





Here, Dp,, is a dipole graph with 2 vertices, n multiple edges and Dp*" is a general- 
ized dipole graph with 2 vertices, n multiple edges, and one vertex with k bouquets 
and another, | bouquets. Comparing the semi-arc automorphism groups in the sec- 
ond column with automorphism groups of graphs in the first column in table 3.1, 
it is easy to note that the semi-arc automorphism group are the same as the auto- 
morphism group in the first two cases. In fact, it is so by the following Theorem 
1.3.1. 


Chapter 1 Preliminary 15 


For Vg € AutI’, there is also an induced action g|? on Xi(T), g:Xi(T) > 


i 
2 


Xi(L), as follows: 


i 
2 


Veu € X1(T), g(eu) = (9(€) 9(u)- 


All induced action of the elements in AutI on Xi(T) is denoted by AutI'|?. Notice 
that 


Aut © Autl’|?. 


We have the following result. 


Theorem 1.3.1 For a graph T without loops, 


AutiP = AutI|?. 


Proof By the definition, we only need to prove that for Ve € Autil’, = G2 Ir € 
AutTP and G2 = é|2. In fact, for any Vey, fr € Xi(T), where, e = uv € E(I) and 
f=cxy € E(I), if 


G2 (Eu) = ce 


then by the definition, we know that 


G2 (ey) a Fy: 
Whence, E1(e) = 7. That is; &1|r € Aut. 
Now since there is not a loop in T, we know that € 1 lr = idp if and only if 
G3 = idp. Therefore, G3 is induced by flr on Xi(T), that is, 


AutiP = Autl|?. 


Notice that for a given graph I, X1(T) = Xz, if we equal e, to e and e, to Ge 
for an edge e = uv € E(L). 
For a given map M = (%.,3,P) underlying a graph I, we have known that 


AutM|p < AutDI, which made us to extend the action of an automorphism g of 


Chapter 1 Preliminary 16 


the graph [ on %,3 with X = E(I) to get automorphisms of a map induced by 


automorphisms of its underlying graph. More detail, we can get the following result. 


Theorem 1.3.2 Two maps M, = (%a,6,P1) and Mz = (Xu,5, P2) underlying a graph 
[ are 

(i) equivalent iff there is an element ¢ € Autil such that PS =P and 

(ii isomorphic iff there is an element ¢ € AutiP such that PS = Pz or PS = 
Pee: 


Proof By the definition of equivalence between maps, if & is an equivalence 
between M, and Mbp, then « is an isomorphism between M, and My, induced by an 


automorphism 1 € AutI’. Notice that 


Aut = Autl]2 < Aut... 


Whence, we know that . € Aut 1 Ae 

Now if there is a ¢ € AutiI such that PS = Po, then Vez € Xi(T), Glen) = 
C(€)c(z). Now assume that e = (x,y) € E(L), then by our convention, we know that 
ife, =e € Xqg, then e, = Ge. Now by the definition of an automorphism on the 
semi-arc set Xi(T), if ¢(€z) = fu, where f = (u,v), then there must be ¢(e,) = fo. 
Notice that Xi) = Xg. We know that ¢(e,) = ¢(Ge) = Bf = fr. We can also 
extend the action of ¢ on X1(P) to %a,g by C(ae) = aC(e). Whence, we know that 
Vee Aaa; 


ac(e) = Cale), B¢(e) = ¢B(e) and P(e) = Pa(e). 
Therefore, the extend action of ¢ on 3 is an isomorphism between the map M, 
and Mz. Whence, ¢ is an equivalence between the map MM, and Mp. So the assertion 
in (2) is true. 
For the assertion in (77), if there is an element ¢ € Aut 1 I such that PS = Po, 
then the map MM, is isomorphic to Mo. If PS = P,', then P?* = Po. The map My 
is also isomorphic to M3. This is the sufficiency of (77). 


By the definition of an isomorphism € between maps MM, and M2, we know that 
Varn € Mee is 


a€(x) = Ea(x), B€(x) = €(x) and Pr (x) = Po(z). 


Chapter 1 Preliminary 17 


By the convention, the condition 


BE(x) = B(x) and Pi (x) = P22). 
is just the condition of an automorphism € or a& on X 1 (I). Whence, the assertion 


in (iz) is also true. 4 


3.2 A scheme for enumerating maps underlying a graph 


For a given graph I’, denoted by €9(L), E* (IL) and €4(L) the sets of embeddings 
of [I on the orientable surfaces, on the non-orientable surfaces and on the locally 
orientable surfaces, respectively. For determining the number of non-equivalent 
embeddings of a graph on surfaces and non-isomorphic unrooted maps underlying a 
graph, another form of the Theorem 1.3.2 using the group action idea is need, which 


is stated as follows. 


Theorem 1.3.3 For two maps M, = (%4,8,P1) and My = (Xa,8,P2) underlying a 
graph T’, then 

(i) My, Mz are equivalent iff Mi, Mz are in one orbits of Autil action on 
Xi); 

(ii) M,, Mz are isomorphic iff M1, Mz are in one orbits of Autilx 2 > 


action on Xq,g- 


Now we can established a scheme for enumerating the number of non-isomorphic 
unrooted maps and non-equivalent embeddings in a given set of embeddings of a 


graph on surfaces by using the Burnside Lemma as the following. 


Theorem 1.3.4 For a given graph T, let E c E+(T), then the numbers n(€,T) and 
n(E, TL) of non-isomorphic unrooted maps and non-equivalent embeddings in E are 


respective 


n(€,T)=-—— YX |ar(a)|, 


2\Auti. geAutyT 


where, ®1(g) ={P|P € E and P9 =P or P* = P} and 


Chapter 1 Preliminary 18 


1 
== ® 


yoann 
where, ®o(g) = {P|P € E and PY =P}. 


Proof Define the group H = Aut 1 [x <a>. Then by the Burnside Lemma 
and the Theorem 1.3.3, we get that 


1 
gEH 
where, (9) = {P|P € € and P¥ = P}. Now |H| = 2|Autil’'|. Notice that if 
PI =P, then P” F P, and if P9* = P, then P? 4 P. Whence, ®1(g)  ®1(ga) = 0. 


We have that 


1 
n[€,T) = 3 Autyl] S* |®i(g)], 


E€AutiT 
2 2 


where, ®;(g) ={P|P € € and PY = P or P% = PH. 


A similar proof enables us to obtain that 


1 
iicoge Bi = age Ay ® 9)\; 
EP) = Ta ge 
where, ®o(g) = {P|P € E and PY =P}. h 


From the Theorem 1.3.4, we get the following results. 


Corollary 1.3.1 The numbers n°(T),n%(L) and n4(L) of non-isomorphic unrooted 
orientable maps ,non-orientable maps and locally orientable maps underlying a graph 


[ are respective 


1 
O O 
n°(T) == ——_ So |®P(g)|;._ (1-3-1) 
2|AutiP| g€Autil : 
2 
1 
N N 
®M=—-— FY (OX@ (132) 
(C) 2|AutiT| geAut,T t 
2 
1 
L L 
eP)=- > — > [el (1.33) 
(T) 2|AutiP| ge Aa t 
2. 


Chapter 1 Preliminary 19 


where, ®9(g) = {P|P € E°(L) and P9 = P or P%* = P}, ON(g) ={P|P € EX (LT) 
and PI =P or P9* = P}, O4(g) = {P|P € EX(T) and P9 =P or P%* = P}. 


Corollary 1.3.2 The numbers 7° (LT), 7 (1) and n*(L) of non-equivalent embeddings 


of a graph T on orientable ,non-orientable and locally orientable surfaces are respec- 


tive 
1 
O O 
DS) ea JO2(g)|; (1.8.4) 
|Aut.D| a 
1 
N N 
Se JP2(g)|; (1.3.5) 
|AutiP| one ° 
MO) =qa LY l4Ol (36) 
| uta | geAuby 


where, ®9(g) = {P|P € E°(T) and PY = P}, ON(g) = {P|P € EN(L) and PY = 
P}, B(g) ={P|P € EX(L) and PY = Ph. 


For a simple graph T, since Aut 1 IT = AutI by the Theorem 1.3.1, the formula 
(1.3.4) is just the scheme used for counting the non-equivalent embeddings of a 
complete graph, a complete bipartite graph in the references [6], [54] — [55], [70]. For 
an asymmetric graphT, that is, Aut 1 I = idp, we get the numbers of non-isomorphic 
maps underlying a graph [I and the numbers of non-equivalent embeddings of the 
graph [ by the Corollary 1.3.1 and 1.3.2 as follows. 


Theorem 1.3.5 The numbers n°(L), nX(L) and n4¥(L) of non-isomorphic unrooted 
maps on orientable, non-orientable surface or locally surface with an asymmetric 


underlying graph VT are respective 


and 


Chapter 1 Preliminary 20 


nT) = (2° — >) TT. (lv) - 1), 


veV(T) 
where, 3(I) is the Betti number of the graph T. 
The numbers 7° (T), 7% (1) and n* (1) of non-equivalent embeddings of an asym- 


metric underlying graph TV’ are respective 


and 


§4. A relation among the total embeddings and rooted maps of a 


graph on genus 


4.1 The rooted total map and embedding polynomial of a graph 


For a given graph [ with maximum valency > 3, assume that r;([),7r;([),7 > 0 
are respectively the numbers of rooted maps with an underlying graph [ on the 
orientable surface with genus y(I‘) +7 — 1 and on the non-orientable surface with 
genus 7(I}) + 7 — 1, where y([f) and 7(I) denote the minimum orientable genus 
and minimum non-orientable genus of the graph I, respectively. Define its rooted 
orientable map polynomial r{U|(x) , rooted non-orientable map polynomial r|T|(x) 


and rooted total map polynomial R[T|(x) on genus by: 


Chapter 1 Preliminary 21 


and 
RU|(z) = Sori(T)a* + So A(T) 2. 
i>0 i>1 
The total number of orientable embeddings of [ is [J] (d— 1)! and non- 
deD(P) 
orientable embeddings is (2°")—1) J] (d—1)!, where D(L) is its valency sequence. 
deD(P) 


Now let g;(I) and g;([), i > 0 respectively be the number of embeddings of [ on 
the orientable surface with genus 7(I})-+7—1 and on the non-orientable surface with 
genus 7([) + 7-1. The orientable genus polynomial g|V|(x) , non-orientable genus 


polynomial g|['|(a) and total genus polynomial G[T|(x) of T are defined by 


gIT\(2) = 7 gi(T a", 


AIE](2) = HT)! 
and - 


GIT|(x) = do ai(P)2" + 0 G(T) 2. 


i>0 i>1 
The orientable genus polynomial g[I'](x) is introduced by Gross and Furst in 
[23], and in [19], [23]—|24], the orientable genus polynomials of a necklace, a bouquet, 
a closed-end ladder and a cobblestone are determined. The total genus polynomial is 
introduced by Chern et al. in [13], and in [31], recurrence relations for the total genus 
polynomial of a bouquet and a dipole are found. The rooted orientable map polyno- 
mial is introduced in [43] — [44], [47] and the rooted non-orientable map polynomial 
in [48]. All the polynomials r|[](x),7[](x), RIT ](x) and g|T](x), g[P] (x), GIL] (x) are 
finite by the properties of embeddings of [’ on surfaces. 
Now we establish relations of r|['|(x) with g[I'|(x), 7[F](x) with g/l ](a) and 
RIT](x) with G[T](z) as follows. 


Lemma 1.4.1([25][45]) For a given map M, the number of non-isomorphic rooted 


maps by rooting on M is 


4de(M) 
|AutM|’ 


Chapter 1 Preliminary 22 


where e(M) is the number of edges in M. 


Theorem 1.4.1 For a given graph T, 


|AutaPr[P](x) = 2e(P)g{l'](x), 


|AutaDfPE](x) = 2e(L)B{C](x) 


and 


|AutgP|RIP|(x) = 2e(L)GIP|(x), 


where Autil and <(I’) denote the semi-arc automorphism group and the size of T, 


respectively. 


Proof For an integer k, denotes by M;(T, S) all the non-isomorphic unrooted 
maps on an orientable surface S with genus 7([1) +k —1. According to the Lemma 
1.4.1, we know that 


4de(M) 

r,(L) = TT aE Pee 

MeMmpr,s) /AutM| 
4e(T) |AutiPx | 


|AutiPx <a> | vemurs |AutM/| 


) 


Aut; Tx<a 
Since |Auti Px Sy S| = |(Auti Tx <a>)m||M a wl and |(AutiP x 


<a >)m|= |AutM], we have that 


r(T) = — ~~ (| 


|AutisPx 0 Sl ihe 


Aut1Tx<a> 
2 


Mx (T,S) 
2e(P) gx (LP) 
|Aut,P| 
Therefore, we get that 
|Aut sD |r[I’](x) a |Aut2P| Sor (L)x' 


i>0 


Chapter 1 Preliminary 23 


= >> lAutalri(P)x’ 


i>0 
= di2e(V)gi(P)a* = 2e(P)g[L] (2). 
i>0 
Similarly, let MAT, S ) be all the non-isomorphic unrooted maps on an non- 
orientable surface S' with genus ¥([) +k —1. Similar to the proof for orientable 


case, we can get that 


xT) = Ae (T) |AutsPx <a>| 
WY? VAutaPx <a>] oo |AutM] 
2 MEM; (T,S) 
4e(T) AutyPx<a> 
= |Mo 2 | 
|AutiPx <a>| exe s 
2e(1)ge(L) 
|AutiP| 


Therefore, we also get that 


|Auta PEP] x) = >) |Auti DF (L)x' 


120 


= So 2e(K)g(De! = 2(0)GITI (a). 


i=0 


Notice that 


and 


GIP \(2) = To gi(P)a* + GP) 0. 


i>0 i>1 
By the previous discussion, we know that for k > 0, 
_ 2e(I’)gx(T’) 


rly = “TAutyry and r;(T) 


_ (DVT) 
|Aut,P| ; 


Therefore, we get that 


Chapter 1 Preliminary 24 


JAutaP|RIP]@&) = |Autal|(Qon(P)x' + 0 


i>0 i>l 
= >- [Auta Pr(T )x? ‘+ So [Aut Pla (L es 
i>0 i>l 
= So 2c(P)g(P)x' + >> 2e(V)gi(V)x™ = 2e(T)GIT] (2). 
i>0 i>0 
This completes the proof. h 


Corollary 1.4.1 Let be [ a graph and s > 0 be an integer. If r.(1) and g,(L) are 
the numbers of rooted maps underlying the graph V and embeddings of TV on a locally 


orientable surface of genus s, respectively, then 
|Autil|r5(L) = 2e(T)g,(T). 


4.2 The number of rooted maps underlying a graph on genus 


The Corollary 1.4.1 in the previous section can be used to find the implicit 
relations among r[I|(x), 7[[](a) or RIT|(x) if the implicit relations among g|I|(x), 
g{V'|(z) or G[D](x) are known, and vice via. 


Denote the variable vector (x1, 22,---) by x, 


r(T) = (- ae r2(T), m(T), ro(T), ri(T), ro(T), = os 


g(T) = e ty G(T), (1), go(T), nT), g(T), a a 


The r([f’) and g(I’) are called the rooted map sequence and the embedding sequence 
of the graph L. 
Define a function F(x, y) to be y-linear if it can be represented as the following 


form 


F(x,y) = f(X1,£2,+-*) + h(x, %2,°° Soy + I( (£1, L2,° pS AC (y), 
wel AEO 


where, J denotes a subset of index and © a set of linear operators. Notice that 
f(@1,%2,--+) = F(x,0), where 0 = (0,0,---). We have the following general result. 


25 


Chapter 1 Preliminary 


Theorem 1.4.2 Let G be a graph family and H CG. If their embedding sequences 


gl), 0 € H, satisfies the equation 





then its rooted map sequences r({),l € H satisfies the equation 
|AutiI ; 
(2, 2¢(T) aR = eo) 


and vice via, if the rooted map sequences r(V),l € H satisfies the equation 


Fr(,(T)) = 0, (4.2) 


then its embedding sequences g(T),l € H satisfies the equation 


2e(T) 
E —— 41 )) = 0. 
Even more, assume the function F(x, y) is y-linear and ah: . € H is a constant. 


If the embedding sequences g(V),l € H satisfies the equation (4.1), then 


Fxg, r(T)) = 0, 


2e(L) —1)F(za, 0) and vice via, if its rooted map sequence 


where Fala, y) = Fle) + (ge 
gf), € H satisfies the equation (4.2), then 





Fy (a, g(P)) = 0. 
: |Autil| 
where FR = F(a, y) + (saxty —1)F(z, 0). 
Proof According to the Corollary 1.4.1 in this chapter, for any integer s > 0 
and [ € H, we know that 


|AutaD'|r.(L) = 


Whence, 


26 


Chapter 1 Preliminary 


and 


r |Autil 
gl) = Sop? 
Therefore, if the embedding sequences g(I‘),  € H satisfies the equation (4.1), 
then 








|Aut iD r ; 
H\X, 2e(T) r )) ear iaees) 
and vice via, if the rooted map sequences r(T'),’ € H satisfies the equation (4.2), 
then 
2e(T) 
FE ——9(T))=0. 


Now assume that Fy,(x,y) is a y-linear function and has the following form 


Fy (x, y) = F(@1, 2a,**) a h(wi;@2,* Soy + I( (Pig Baye ee Aly 
tel AcEO 


where O is a set of linear operators. If Fy(x, g(I)) = 0, that is 











T Bin Wa.) ay Bs ie re g(T) + Ua, t2,°-:) > A(g(T)) = 0, 
i€l,EH ACOTCH 
we get that 
f( Dae he (So 
X1,%2,°°° T U1,%2,°°° T% 

ictren 2E(T) 

I |AutI 

= v1, v2, Pa er Tr — 

acoren —-2€(T) 


Since A € O is a linear operator and wat Tat ,l € His a constant, we also have 





|AutiP| 
PORERE DS 2 peg, ae 
|AutiD| 
F—U(e1,02---) YS AG(L)) =0, 





2e(T) AcOTEH 


Chapter 1 Preliminary 27 


that is, 


2<(L) 


Trae, Tete FMI) Se nT) +H aa) Do Alar) = 0. 


i€l1,TEH ACO TECH 


Therefore, we get that 


Similarly, if 


then we can also get that 


Fr(x, g(P)) = 0. 


This completes the proof. h 


Corollary 1.4.2 Let G be a graph family and H CG. If the embedding sequence 
gL) of a graph T €G satisfies a recursive relation 


d a(t, P)gi(P) = 0, 


ie JTEH 
where J is the set of index, then the rooted map sequence r(I) satisfies a recursive 


relation 


a(i,T)|AutiT| 
21 ) me 
iG J.TEH 2¢(T’) 


and vice via. 


A typical example of the Corollary 1.4.2 is the graph family bouquets B,,,n > 
1. Notice that in [24], the following recursive relation for the number g,,(n) of 
embeddings of a bouquet B, on an orientable surface with genus m for n > 2 was 


found. 


(n+ 1)gm(n) = 4(2n —1)(2n — 3)(n —1)?(n — 2)gm—1(n — 2) 
+ 4(2n —1)(n —1)gm(n — 1). 


Chapter 1 Preliminary 28 


and with the boundary conditions 


Gm(n) = 0 if m <0 orn < 0; 

go(0) = go(1) = 1 and gm(0) = gm(1) = 0 for m > 0; 

90(2) = 4, 91(2) = 2, 9m(2) = 0 for m > 1. 

Since |Aut 1 B,| = 2”n!, we get the following recursive relation for the number 
T'm(n) of rooted maps on an orientable surface of genus m underlying a graph B,, by 
the Corollary 1.4.2 


(n? —1)(n—2)rm(n) = (2n—1)(2n —3)(n — 1)?(n — 2)rm_i(n — 2) 
+ 2(2n —1)(n—1)(n—-2)rm(n — 1), 


and with the boundary conditions 
Peli) =Orat 1 < 0-or <0; 
ro (OV = 760) = Land r4,(0) = ta(l) = 0 for m= 0; 
fo(2) = 2,712) = Lon?) =0 for m= 1 


Corollary 1.4.3 Let G be a graph family and H CG. If the embedding sequences 
QU), P €G satisfies an operator equation 


> A(g(P)) = 9, 


AEO,TEH 
where O denotes a set of linear operators, then the rooted map sequences r(C), € H 


satisfies an operator equation 


|Autil 


ACO TECH 





and vice via. 


Let 6 = (01, 6,---,%)  2n, ice., 3 6; = 2n with positive integers 6;. Kwak 
and Shim introduced three linear pean T,0 and A to find the total genus 
polynomial of the sins B,,n => 1 in [31], which are defined s follows. 

Denotes by z and zg’ = 1/2 the multivariate monomials 0 zp, and 1/ Il 26,5 
where 0 = (61, 02,--+,0;) / 2n. Then the linear operators I, fe) and A are defined 
by 


Chapter 1 Preliminary 29 











and 








A(x) = Yo 26,0; ao} + (EE aah] 


1<i<j<k 595 20; 70; 
Denotes by i[B,](z;) the sum of all monomial zg or 1/z taken over all embed- 


dings of B,, into an orientable or non-orientable surface, that is 


*[Bn](zj) = D> io(Bn)zo + > to(Bn)z9", 


OF2n OF2Qn 
where, ig(B,) and ig(B,) denote the number of embeddings of B, into orientable 
and non-orientable surface of region type 0. They proved in [31] that 


A 


wl 
[Bnsi](%) = (P+ + Aji[Br](z) =(P+0 + ANS + 2). 
and 
1 
G|Brsil(x ie (T + S) + A (— 29 sh ie for j>1 and (Cx): 

Where, (Cx) denotes the condition 

(Cx): replacing the power 1+n—2i of x byt ift > 0 and —(1+n+4+i) by -7 
ifi<0. 
Since 


SS erg ih 
2e(Bn) 2n ase 
and [, 0, A are linear, by the Corollary 1.4.3 we know that 

















(C+ 0+ A)i[B,](z;) 
RiBriil(2) = Se for j>1 and (Cx) 
(r+o0 Ay + 2?) 
7 aa is for j>1 and (Cx): 
TI 2kk! 


k=1 


Chapter 1 Preliminary 


30 


For example, calculation shows that 





1 
RI[Bi\(2) =2+4+-; 
x 
4 
R[Bo\(z) =2+a+— +3; 
41 42 22 
R[B3\(z) = = Pa oe + 54 10a; 


and 





ba Ae OTe: 


Chapter 2. On the Automorphisms of a Klein Surface 
and a s-Manifold 


Many papers concerned the automorphisms of a Klein surface, such as,{1], [15], 
[26], [38] for a Riemann surface by using Fuchsian group and [9] — [10], [21] for a 
Klein surface without boundary by using NEC groups. Since maps is a natural 
model for the Klein surfaces, an even more efficient approach is, perhaps, by using 
the combinatorial map theory. Establishing some classical results again and finding 


their combinatorial refinement are the central topics in this chapter. 


§1. An algebraic definition of a voltage map 


1.1 Coverings of a map 


For two maps M = (X4,3,P) and M = (X.,g,P), call the map M covering the 
map M if there is a mapping 7 : Xn, — Xy,¢ such that Vr € Raa 


an(x) = na(x), Bx(x) = r(x) and rP(x) = Pr(x). 


The mapping 7 is called a covering mapping. For Vx € Xq,3, define the quadricell 
set 7 '(x) by 


a(x) = {&|% € (Xy,g and 1(#) = cx}. 


We have the following result. 


Lemma 2.1.1 Let 7: Xug — Xag be a covering mapping. Then for any two 
quadricells x1, 22 € Xap, 

(i) |x (x1) | = [7 (22)I. 

(it) If v1 A x2, then a*(a1) 0 \(a2) = 9. 


Proof (i) By the definition of a map, for 71,72 € Xy,, there exists an element 


0 € WV; =< a,8,P > such that ro = o(21). 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 32 


Since 7 is an covering mapping from M to M , it is commutative with a, 3 and 


P. Whence, 7 is also commutative with ao. Therefore, 


m*(2) = 7 *(o(a1)) = a(n" (a1)). 


Notice that o € Vy is an 1—1 mapping on %,. Hence, |m~1(21)| = |r71(x2)|- 

(ii) If 2, # xq and there exists an element y € m~'(r1)(\m7'(x2), then there 
must be x, = 7(y) = ®. Contradicts the assumption. h 

The relation of a covering mapping with an isomorphism is in the following 


theorem. 


Theorem 2.1.1 Let 7 : An — Xq,3 be a covering mapping. Then 7 is an isomor- 


phism iff 7 is an 1 — 1 mapping. 


Proof If 7 is an isomorphism between the maps M = (%,,a,P) and M = 
(X,3,P), then it must be an 1 — 1 mapping by the definition, and vice via. L 
A covering mapping 7 from M to M naturally induces a mapping 7* by the 


following condition: 


Va € Xo8,9 € AutM,n*:9—> ngn*(2). 


We have the following result. 


Theorem 2.1.2 If 7m : Vag — Xo,g 18 @ covering mapping, then the induced mapping 


Ba 


m* 1s a homomorphism from AutM to AutM. 


Proof First, we prove that for Vg € AutM and x € Xoo, 7*(g) € AutM. 
Notice that for Vg € AutM and x € X,.g, 


mga '(x) = m(gn*(2)) € Xa, 


and Vx1,%2 € Xa, if v1 # ©, then tgm~\(x1) A Tgm~'(x2). Otherwise, assume 
that 


ngn*(ay) = gn'(a2) = 20 € Xap, 


then we have that x; = mg~'2~1(xq) = x. Contradicts to the assumption. 


By the definition, for x € V3 we get that 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 33 


n*a(x) = tgn—'a(x) = rgan (x) = magn '(x) = angn (xz) = ar*(z), 


n* B(x) = gn 'B(x) = 1gBx* (a) = nBgn\(x) = Brgn*(x) = Br* (x). 


Notice that 7(P) =P. We get that 


m* P(x) = aga P(x) = ngPr-' (x) = tP gn '(x) = Pagar (x) = Pr*(z). 


Therefore, we get that mgm! € AutM, ie., 7*: AutM > AutM. 
Now we prove that 7* is a homomorphism from AutM to AutM. In fact, for 
Vgi, go © AutM, we have that 


*(gig2) = T(gige)m* = (mg17~')(mgaM~") = 1*(gi)m*(g2). 
Whence, 7* : Aut — AutM is a homomorphism. h 


1.2 Voltage maps 


For creating a homomorphism between Klein surfaces, voltage maps are exten- 
sively used, which is introduced by Gustin in 1963 and extensively used by Youngs 
in 1960s for proving the Heawood map coloring theorem and generalized by Gross 
in 1974 ([22]). Now it already become a powerful approach for getting regular maps 
on a surface, see [5], [7], [56] — [57], [65]], especially, [56] — [57]. It often appears as an 
embedded voltage graph in references. Notice that by using the voltage graph the- 
ory, the 2-factorable graphs are enumerated in [51]. Now we give a purely algebraic 
definition for voltage maps, not using geometrical intuition and establish its theory 


in this section and the next section again. 


Definition 2.1.1 Let M = (Xu,3,P) be a map and G a finite group. Call a pair 
(M,v) a voltage map with group G if 0: Xag — G, satisfying the following condi- 
tion: 


(i) Va € Xyg, B(axr) = V(x), V(aBx) = 0(Bx) = 0-1(z); 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 34 


(ii) VF = (a,y,---,2z)(Gz,---, Gy, Gx) € F(M), the face set of M, V(F) = 
U(x)V(y)---0(z) and < V(F)|F € F(u),u € V(M) >= G, where, F(u) denotes all 


the faces incident with the vertex u. 


For a given voltage graph (/,¥V), define 


Xa 3° = Xo,B xG 


Pe I [1 (oe. Yo. - ++» 29) (Q%q, +++, BYg, Ly), 


(2,Y,++,2)(az,-,ay,axr)eV (M) gEG 


and 


B= JT (aq, (Bx) ga(e)). 


LEX 8 ,9€G 
where, we use u, denoting an element (u,g) € Va,g x G. 

It can be shown that M” = (4X0 ge, P”) also satisfying the conditions of a map 
with the same orientation as the map WM. Hence, we can define the lifting map of a 


voltage map as follows. 


Definition 2.1.2 For a voltage map (M,¥) with group G, the map M” = (X24,P”) 
is called its lifting map. 
For a vertex v = (C)(aCa~') € V(M), denote by {C} the quadricells in the 


cycle C’. The following numerical result is obvious by the definition of a lifting map. 


Lemma 2.1.2 The numbers of vertices and edges in the lifting map M” are respective 
v(M”) =v(M)|G| and «(M”) = «(M)|G| 


Lemma 2.1.3 Let F = (C*)(aC*a7!) be a face in the map M. Then there are 
|G|/o(F) faces in the lifting map M” with length |F\o(F) lifted from the face F, 


where o(F') denotes the order of [|] U(x) in the group G. 
xE{C} 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 39 


Proof Let F = (u,v---,w)(Gw,---, Gv, Gu) be a face in the map M and k is 
the length of F’. Then, by the definition, for Vg € G, the conjugate cycles 


(C*)" = (Ug, Ugo(u)s* + Ugd(F)s Vgo(F)O(u) Woo (R)2s* * +» WygeF)-1(F)) 


Bigs UgoGi)s* > Mei Fs Ved POG Wea os WagoF)-1(p)) Bt. 


is a face in M” with length ko(F). Therefore, there are |G|/o(F) faces in the lifting 
map M”. altogether. b. 
Therefore,we get that 


Theorem 2.1.3 The Euler characteristic y(M”) of the lifting map M® of the voltage 
map (M,G) is 


(MP) =|G\x(M)+  S (-1+—)), 


m€O(F(M)) a 
where O(F (M)) denotes the order o(F’) set of the faces in M. 


Proof According to the Lemma 2.1.2 and 2.1.3, the lifting map M” has |G|v(M) 


vertices, |Gle(M) edges and |G| > — = faces. Therefore, we get that 
me€O(F(M)) 


x(M") = u(M") —e(M") + o(M") 








= |Gly(M)-|GleM) + iG) & — 
meO(F(M)) 
= |G\x(M)-e(M)+ =) 
m€eO(F(M)) 
= |14lo(M)+ > (-1+=)) : 


me€O(F(M)) 


§2. Combinatorial conditions for a group being that of a map 


Locally characterizing that an automorphism of a voltage map is that of its 
lifting is well-done in the references [40] — [41]. Among them, a typical result is the 


following: 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 36 


An automorphism ¢ of a map M with voltage assignment 0 — G is an auto- 
morphism of its lifting map M” if for each face F with 0(F) =1e, Y(¢(F)) =1e. 


Since the central topic in this chapter is found what a finite group is an automor- 
phism group of a map, i.e., a global question, the idea used in the references [40]—[41] 


are not applicable. New approach should be used. 


2.1 Combinatorial conditions for an automorphism group of a map 


First, we characterize an automorphism group of a map. 
A permutation group G action on (2 is called fixed-free if G, = 1g for Vx € Q. 
We have the following. 


Lemma 2.2.1 Any automorphism group G of a map M = (%4,g,P) is fixed-free on 
Aces 


Proof For Vz € X%q,g,since G < AutM, we get that G, < (AutM),. Notice that 
(AutM), = 1¢. Whence, we know that G, = 1g, ie., G is fixed-free. b 
Notice that the automorphism group of a lifting map has a obvious subgroup, 


determined by the following lemma. 


Lemma 2.2.2 Let M” be a lifting map by the voltage assignment 0 : Xug > G. 
Then G is isomorphic to a fixed-free subgroup of AutM® on V(M”). 


Proof For Vg € G, we prove that the induced action g* : XQ g0 > X,0,g0 by 
g* : L_, — Lgn is an automorphism of the map M”. 

In fact, g* is a mapping on Xo go and for Vr, € XQ» gv, we get g* : Lg-1y > Ly. 

Now if for tn, yp € Vqege,0n F Ys, we have that g*(xn) = g* (yf), that is, 
XLgh = Yof, by the definition, we must have that x = y and gh = gf, ie., h = f. 
Whence, vp, = yf, contradicts to the assumption. Therefore, g* is 1 — 1 on Xye go. 

We prove that for x, € Ye, g* ia commutative with a”, 3” and P”. Notice 


that 


Ga xy = 9 (AX)u = (AX) gu = AXgu = ag" (Lu); 


9" B” (xu) = J (BX) w9(a) = (GX) gu9(a) = PX guo(c) = Cee) = Og" Ga) 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 37 


and 


= g Il RGA are eer A Oy) (by) 
(2,y,°++,2)(az,-,ay,ax)EV (M) uEeG 


= Oo thy = You 


= Il Il (bau Yoqus** "5 Bau) Oe, “5, QAYguy Oss) (Leis) 
(2,y,---,2)(az,--,ay,arz)EV(M) gueG 


= P" ou) = Pog ei) 


Therefore, g* is an automorphism of the lifting map M”. 
To see g* is fixed-free on V(M), choose Vu = (Xn, Yny* ++, Zn) (Zn, °° °; Yn, ATH) E 
V(M),heEG. If g*(u) = yu, ie., 


(Pai Yoho "5 oi) (AZgr, “7+, QYgh) AX gh) = (ons Yass *s Zn)(Zp, "7", QYh; ALp). 


Assume that tn = wp, where wp € {Xn Yn, °° +s Zn, ALA, UYn,* ++, 2%}. By the 
definition, there must be that x = w and gh = h. Therefore, g = 1g, i.e., Vg € G, 
g® is fixed-free on V(M). 

Now define 7 : g* — g. Then 7 is an isomorphism between the action of 
elements in G on 4X,» go and the group G itself. h 

According to the Lemma 2.2.1, given a map M and a group G x AutM, we 
can define a quotient map M/G = (X4,8/G,P/G) as follows. 


Xo,6/G = {x?|x € Xa gh, 


where x° denotes an orbit of G action on %,,3 containing 2 and 


PYG = Il (x? y%,---)(--,ay%, ax), 


(@,Y,5z)(az,--,axy,ax) EV (M) 
since G' action on %,,g is fixed-free. 
Notice that the map M may be not a regular covering of its quotient map M/G. 
We have the following theorem characterizing a fixed-free automorphism group of a 
map on V(M). 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 38 


Theorem 2.2.1 An finite group G is a fixed-free automorphism group of a map 
M = (Xag,P) on V(M) iff there is a voltage map (M/G,G) with an assignment 
0: Xag/G— G such that M = (M/G)°. 


Proof The necessity of the condition is already proved in the Lemma 2.2.2. We 
only need to prove its sufficiency. 

Denote by 7: M — M/G the quotient map from M to M/G. For each element 
of m~'(x°), we give it a label. Choose x € 1~1(x@). Assign its label 1: 2 > 216, 
i.e., I(x) = 21,4. Since the group G acting on %y,g is fixed-free, if u € m~'(x°) and 
u = g(x),g € G, we label wu with I(u) = x,. Whence, each element in 77'(r°) is 
labelled by a unique element in G. 

Now we assign voltages on the quotient map M/G = (%,3/G,P/G). If Ga = 
y,y € w *(y®) and the label of y is I(y) = yf,h € G, where, I(y*) = 1g, then 
we assign a voltage h on x°,i.e., J(x%) = h. We should prove this kind of voltage 
assignment is well-done, which means that we must prove that for Vu € 2~1(x) 
with I(v) = 7,7 € G, the label of Gv is l(Gv) = jh. In fact, by the previous labelling 
approach, we know that the label of Gv is 


i(Gv) 


I(Bgx) = (gBx) 
l(gy) = U(ghy") = gh. 


Denote by M' the labelled map M on each element in ¥,,3. Whence, M!' & M. 
By the previous voltage assignment, we also know that M’ is a lifting of the quotient 
map M/G with the voltage assignment J : X,,3/G — G. Therefore, 


M = (M/G)’. 


This completes the proof. h 
According to the Theorem 2.2.1, we get the following result for a group to be 


an automorphism group of a map. 
Theorem 2.2.2 If a group G,G x AutM, is fixed-free on V(M), then 


Glod(M/e)+ XL (1 4+) =x). 


m€O(F(M/G)) mm 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 39 


Proof By the Theorem 2.2.1, we know that there is a voltage assignment 7? on 
the quotient map M//G such that 


M = (M/G)°. 
Applying the Theorem 2.1.3, we know the Euler characteristic of the map M is 


1 
X(M) =|GI(x(M/G)+  d)  (-I+—)). 5 
m€O(F(M/G)) 
Theorem 2.2.2 has some useful corollaries for determining the automorphism 


group of a map. 


Corollary 2.2.1 If M is an orientable map of genus p, G x AutM is fired-free on 
V(M) and the quotient map M/G with genus y, then 


2p — 2 


“H=2+  y . C=) 
meO(F(M/G)) 


|G| 
Particularly, if M/G is planar, then 


2p — 2 
|G| = —————.. 
= ae 2 eee Ce =))) 
m€O(F(M/G)) 
Corollary 2.2.2 If M is a non-orientable map of genus q, G <x AutM is fixed-free 
on V(M) and the quotient map M/G with genus 6, then 


q-2 
G| = ———__4_" ___. 
a =e ee) 
meO(F(M/G)) 


Particularly, if M/G is projective planar, then 


q-—2 
Q See 
aa os a) 
m€O(F(M/G)) 
By applying the Theorem 2.2.1, we can also calculate the Euler characteristic 
of the quotient map, which enables us to get the following result for a group being 


that of a map. 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 40 
Theorem 2.2.3 If a group G,G x AutM, then 


xX(M)+ D7 (@.(9)1 + 18r(9)1) = IGIx(M/G), 


g€G,gAlG 
where, ®,(g) = {v|ju € V(M), v9 = v} and ®;(g) = {ff € F(M), f9 = f}, and if 
G is fixed-free on V(M), then 


x(M)+ D7 |®;(9)| = |GIx(M/G). 


g€G,gAl1e 


Proof By the definition of a quotient map, we know that 


dy(M/G) = orb, ( S> |®.(9 
“a geG 
and 
b¢(M/G) = orbs(G d l&s(9) 
-a gEG 


by applying the Burnside Lemma. Since Gis fixed-free on ¥,3 by the Lemma 2.1, 
we also know that 
e(M) 
IG| 
Applying the Euler-Poincaré formula for the quotient map M/G, we get that 





<(M/G) = 


FIMO! apy Elo 


gEG gcG 
4 = (MG). 
qe ‘er ie 
Whence, we have 
> 182(9)| —e(M) + D7 |®s(9)| = |Glx(M/G). 
geG gEG 


Notice that v(M) = |®,(1¢)|, 6M) = |®r(1e)| and v(M) — e(M)+ ¢(M) = x(). 
We know that 


x(M) + d) (B.(9)1 + 18s(9)1) = 1Gx(M/@). 


g€G,gAlea 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 41 


Now if G is fixed-free on V(M), by the Theorem 2.1, there is a voltage as- 
signment 7 on the quotient map M/G such that M & (M/G)”. According to the 


Lemma 2.1.2, we know that 





v(M) 
v(M/G) = 
IG| 
Whence, > |®,(g)| =v(M) and SS  (|®,(g)| =0. Therefore, we get that 
geG 9¢G,gAla 


x(M)+ dS) [®s(9)1=1Glx(M/G). 5 


g6G.gFlg 
Consider the properties of the group G on F'(/), we get the following interest- 


ing results. 


Corollary 2.2.3 If a finite group G,G x AutM is fixed-free on V(M) and transitive 
on F(M), for example, M is regular and G = AutM, then M/G is an one face map 


and 


x(M) = |G|(x(M/G) — 1) + 6(M) 
Particularly, for an one face map, we know that 


Corollary 2.2.4 For an one face map M, if G, G x AutM is fixed-free on V(M), 
then 


XM) = 1 = |G (x G)-—1), 
and |G|, especially, |AutM| is an integer factor of x(M) — 1. 
Remark 2.2.1 For an one face planar map, i.e., the plane tree, the only fixed-free 


automorphism group on its vertices is the trivial group by the Corollary 2.4. 


2.2 The measures on a map 


On the classical geometry, its central question is to determine the measures on 
the objects, such as the distance, angle, area, volume, curvature, .... For maps being 
a combinatorial model of Klein surfaces, we also wish to introduce various measures 


on a map and enlarge its application filed to other branch of mathematics.. 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 42 


2.2.1 The angle on a map 


Foramap M = (%5,P), 2 © Xa,g, the permutation pair {(1, Px), (ax, P~'ax)} 
is called an angle incident with x, which is introduced by Tutte in [66]. We prove 
in this section that any automorphism of a map is a conformal mapping and affirm 
the Theorem 1.2.7 in Chapter 1 again. 


Define an angle transformation © of angles of a map M = (%,,g,P) as follows. 


O= |] (2,Pz). 


tEXa,g 


Then we have 


Theorem 2.2.4 Any automorphism of a map M = (X4,8,P) is conformal. 


Proof By the definition, for Vg € AutM, we know that 


ag =ga, Bg = gG and Pg = gP. 


Therefore, for Vz € Xa,3, we have 


Og(x) = (g(x), Pg(x)) 


and 


gO(x) = g(x, Px) = (9(2), Pg(x)). 


Whence, we get that for Vz € X.5, Og(x) = gO(x). Therefore, we get that 
Og = gO, ji.e., Og ' =O. 

Since for Vz € Xa,e, gOg7'(x) = (g(x), Pg(x)) and O(x) = (x, P(zx)), we have 
that 


(g(x), Pg(@)) = (@, P(x). 
That is, g is a conformal mapping. h 


2.2.2 The non-Euclid area on a map 


For a given voltage map (V,G), its non-Euclid area ~(M,G) is defined by 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 43 


w(M,G) =2n(-y(M)+ (14) 
meO(F(M)) 


Particularly, since any map M can be viewed as a voltage map (M/,1¢), we get the 
non-Euclid area of a map MW 
w(M) = w(M,1¢@) = —27x(M). 


Notice that the area of a map is only dependent on the genus of the surface. 


We know the following result. 


Theorem 2.2.5 Two maps on one surface have the same non-Euclid area. 


By the non-Euclid area, we get the Riemann-Hurwitz formula in Klein surface 


theory for a map in the following result. 
Theorem 2.2.6 IfG = AutM is fixed-free on V(M), then 


wt) 
Cl = TMG, 


where 0 is constructed in the proof of the Theorem 2.2.1. 


Proof According to the Theorem 2.2.2, we know that 


—x(M) 


OF Gi GIFs) 
m€O(F(M)) 
_ —2nx(M) __ HWM), 
a(x) lt) eOM/G, 9) 


As an interesting result, we can obtain the same result for the non-Euclid area 


of a triangle as the classical differential geometry. 


Theorem 2.2.7([42]) The non-Euclid area (A) of a triangle A on a surface S with 


internal angles n, 0,0 1s 


w(A)=n+0+0-7. 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 44 


Proof According to the Theorem 1.2.1 and 2.2.5, we can assume there is a 
triangulation M with internal angles 7,0,0 on S and with an equal non-Euclid area 


on each triangular disk. Then 


o(M)u(A) = p(M) = —2nx(M) 


= —2n(v(M) —«(M) + 4(M)). 


Since M is a triangulation, we know that 


2e(M) = 3¢(M). 


Notice that the sum of all the angles in the triangles on the surface S is 27v(M), 
we get that 


o(M)u(A) = —2n(v(M) — e(M) + ¢(M)) = (2v(M) — o(M))r 
¢(M) 
s(n $9 +0) —7] = 0(M)(n +0 +0—7). 


i=1 


Whence, we get that 


w(A)=n+0+0-7. h 


§3. A combinatorial refinement of Huriwtz theorem 


In 1893, Hurwitz obtained a famous result for the orientation-preserving auto- 
morphism group Aut*S of a Riemann surface S({11][18][22]): 


For a Riemann surface S of genus g(S) > 2, AutTS < 84(g(S) — 1). 


We have known that the maps are the combinatorial model for Klein surfaces, 
especially, the Riemann surfaces. What is its combinatorial counterpart? What we 
can say for the automorphisms of a map? 

For a given graph I, define a graphical property P to be its a kind of subgraphs, 


such as, regular subgraphs, circuits, trees, stars, wheels, ---. Let M = (Xa,8, P) be 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 45 


amap. Call a subset A of ¥,,g has the graphical property P if the underlying graph 
of A has property P. Denote by A(P, M) the set of all the A subset with property 
P inthe map M. 

For refinement the Huriwtz theorem, we get a general combinatorial result in 


the following. 


Theorem 2.3.1 Let M = (%a4,P) be a map. Then for VG x AutM, 


[lo“llv € Viaa)] | [GI 


and 


IG] | [AIACP, M)], 
where, |a,b,---] denotes least common multiple of a, b, ---. 


Proof According to a well-known result in the permutation group theory, for 
Yu € V(M), we know |G| = |G,||v@|. Therefore, |v°| | |G]. Whence, 


[lev € V(M)] | |GI. 


The group G is fixed-free action on %,,g, i.e., V2 € Xa,3, we have |G',| = 1 (see 
also [28]). 

Now we consider the action of the automorphism group G on A(P, M). Notice 
that if A € A(P, M), then then Vg € G,A9) € A(P, M), ie., AP C A(P, M). That 
is, the action of G on A(P, M) is closed. Whence, we can classify the elements in 
A(P, M) by G. For Vz,y € A(P, M), define x ~ y if and only if there is an element 
g,9 € G such that x79 = y. 

Since |G,| = 1, ie., |e@| = |G], we know that each orbit of G action on X.g 
has a same length |G|. By the previous discussion, the action of G on A(P, M) is 
closed, therefore, the length of each orbit of G action on A(P, M) is also |G|. Notice 
that there are |A||A(P, M)| quadricells in A(P, M). We get that 


IG] | [AJA 1). 


This completes the proof. h 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 46 


Choose property P to be tours with each edge appearing at most 2 in the map 
M. Then we get the following results by the Theorem 2.3.1. 


Corollary 2.3.1 Let Trz be the set of tours with each edge appearing 2 times. Then 
for VG x AutM, 
£ 
Al | (lr), t= (t|= Eb >1, re Tra). 


Let Tr, be the set of tours without repeat edges. Then 


fi 
|G| | QU alt= \T| = le 1, T€Tr,). 


Particularly, denote by o(i, 7) the number of faces in M with facial length i and 


singular edges 7, then 


where,(a,b,---) denotes the greatest common divisor of a,b,--:. 


Corollary 2.3.2 Let T be the set of trees in the map M. Then for VG X AutM, 


|G] | (2lti,1 2 1), 


where t; denotes the number of trees with | edges. 


Corollary 2.3.3 Let v; be the number of vertices with valence 1. Then for VG ~X 
AutM, 


IG] | (205,41): 


Theorem 2.3.1 is a combinatorial refinement of the Hurwitz theorem. Applying 


it, we can get the automorphism group of a map as follows. 
Theorem 2.3.2 Let M be an orientable map of genus g(M) > 2. Then for VG x 
Aut*M, 

IG] < 84(g(M) - 1) 


and forYWG x AutM, 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 47 


|G] < 168(g(M) — 1). 





Proof Define the average vertex valence v(M) and the average face valence 


@(M) of a map M by 





v(M aM 221% 


si 


o(M = san y a Sb 


1 
where,v(M),¢(M),¢(M) and ¢; denote the number of vertices, faces, vertices of 
valence 2 and faces of valence 7, respectively. 
Then we know that v(M)v(M) = ¢(M)¢(M) = 2e(M). Whence, v(M) = 


(M) = a“ “) According to the Euler formula, we have that 








v(M) — e(M) + 6(M) = 2— 29(M), 


where,e(V),g(M) denote the number of edges and genus of the map M. We get 
that 





2(g(M) — 1) 
e(M) = AA 
ee oan 
Choose the integers k = [v(M)] and | = [¢(M)]. We have that 


a=¥=9) 
Because 1 — 2 — t = MOBO Re ok Z*. Calculation shows that the 
minimum value ap 1-—<¢- 2 is a and attains the minimum value if and only if 


(hp) = (800) Or Cia): Thee 


e(M < 42(g(M) — 1)). 


According to the Theorem 2.3.1 and its corollaries, we know that |G| < 4e(/M) 
and if G is orientation-preserving, then |G| < 2¢(V7). Whence, 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 48 


IG] < 168(g(M) — 1)) 


and if G is orientation-preserving, then 


IG] < 84(9(M) —1)), 
with equality hold if and only if G = AutM, (k,l) = (8,7) or (7,3). b 


For the automorphism of a Riemann surface, we have 
Corollary 2.3.4 For any Riemann surface S of genus g > 2, 
4g(S) +2 < |AuttS| < 84(g(S) — 1) 
and 
8g(S) +4 < |AutS| < 168(g(S) — 1). 


Proof By the Theorem 1.2.6 and 2.3.2, we know the upper bound for |AutS| and 
|Aut*S|. Now we prove the lower bound. We construct a regular map M;, = (4X, Pr) 


on a Riemann surface of genus g > 2 as follows, where k = 2g + 1. 


Xi, = {%1, LQ,°°°, UE, AL, AT2,° °°, ALE, Bx, Bx, nay Big abr, abr, aaa aBx;,} 


Py = (Zig Q,°°°, Uk, aBxy, aBxr, eg 2 aBx,)(BXx, anes 5/929; Bx, ALE, AX, ax). 


It can be shown that M; is a regular map, and its orientation-preserving auto- 
morphism group Aut* M, =< P; >. Direct calculation shows that if k = 0(mod2), 
My, has 2 faces, and if k = 1, M; is an one face map. Therefore, according to the 
Theorem 1.2.6, we get that 


|AutTS| > 2e(M;) > 4g 4+ 2, 


and 


|AutS| > 4e(M;,) > 8g + 4. h 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 49 


For the non-orientable case, we can also get the bound for the automorphism 


group of a map. 
Theorem 2.3.3 Let M be a non-orientable map of genus g'(M) > 3. Then for 
VG X Aut? M, 

|G] < 42(g'(M) — 2) 


and for VG x AutM, 


IG] < 84(9'(M) — 2), 


with the equality hold iff M is a regular map with vertex valence 3 and face valence 


7 or vice via. 


Proof Similar to the proof of the Theorem 2.3.2, we can also get that 


e(M < 21(9'(M) — 2)) 
and with equality hold if and only if G = AutM and M is a regular map with vertex 
valence 3, face valence 7 or vice via. According to the Corollary 2.3.3, we get that 
IG| < 4e(M) 


and if G is orientation-preserving, then 


|G| < 2e(M). 


Whence, for VG = Aut*M, 


IG] < 42(g'(M) — 2) 


and for VG ~< AutM, 


IG] < 84(g'(M) — 2), 


with the equality hold iff M is a regular map with vertex valence 3 and face valence 


7 or vice via. h 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 500 


Similar to the Hurwtiz theorem for a Riemann surface, we can get the upper 


bound for a Klein surface underlying a non-orientable surface. 
Corollary 2.3.5 For any Klein surface K underlying a non-orientable surface of 
genus q > 3, 

|Aut*K] < 42(q — 2) 


and 


|AutK| < 84(q — 2). 


According to the Theorem 1.2.8, similar to the proof of the Theorem 2.3.2 and 


2.3.3, we get the following result for the automorphisms of an s-manifold as follows. 


Theorem 2.3.4 Let C(T,n) be a closed s-manifold with negative Euler characteristic. 
Then |AutC(T, n)| < 6n and 


|AutC(T,n)| < —21x(C(T,n)), 


with equality hold only if C(T,n) is hyperbolic, where x(C(T,n)) denotes the genus 
of C(T,n). 


Proof The inequality |AutC(T,n)| < 6n is known by the Corollary 2.3.1. Similar 
to the proof of the Theorem 2.3.2, we know that 


—x(C(Z,n)) 
eC Lh) = 
3° ik 
where k = OTA > iv; < 7 and with the equality holds only if k = 7, ie., C(T,n) 
mm) 1 
is hyperbolic. h 


§4. The order of an automorphism of a Klein surface 


Harvey [26] in 1966, Singerman [60] in 1971 and Bujalance [9] in 1983 considered 
the order of an automorphism of a Riemann surface of genus p > 2 and a compact 


non-orientable Klein surface without boundary of genus gq > 3. Their approach is 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold ol 


by using the Fuchsian groups and NEC groups for Klein surfaces. The central idea 
is by applying the Riemann-Hurwitz equation, stated as follows: 
Let G be an NEC graph and G’ be a subgroup of G with finite index. Then 


L(G’) 
L(G) 
where, (G) denotes the non-Euclid area of the group G, which is defined as if 





=[G:G', 


— (9; = [m, sy, ip { aici) ee (Ne, aces eon 


is the signature of the group G, then 


u(G) = anlng+ k—~2 + 3-( 1 —1/m,) FIPS 1 —1/ni;)], 


i=1 j=1 
where, n = 2 if sign(o) = + and n = 1 otherwise. 

Notice that we have introduced the conception of non-Euclid area for the voltage 
maps and have gotten the Riemann-Hurwitz equation in the Theorem 2.2.6 for a 
fixed-free on V(M) group. Similarly, we can find the minimum genus of a map, 
fixed-free on its vertex set by the voltage assignment on its quotient map and the 


maximum order of an automorphism of a map. 


4.1 The minimum genus of a fixed-free automorphism 


Lemma 2.4.1 Let N = Il Dp; Pi < po < +++ < px be the arithmetic decomposition 
of the integer N and m,; S 1,m,|N for i= 1,2,---,k. Then for any integer s > 1, 


Se Soot 


i=l M4 Pi 2 
Proof If s = 0(mod2), it is obvious that 


1 1 1 
Sadie) 3 (he eae 
i=l mm; i=1 Pi Pi 
Now assume that s = 1(mod2) and there are m;, 4 pi,j = 1,2,---,1. If the 


assertion is not true, we must have that 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold O2 





1 1 1 
1——)(l-—1) > 1- >(1-—Y)l 
( Pa ) 2 =a 2 ( - 
Whence, we get that 
1 1 1 1 
1—-—)l >(1-—)l+1-—— >(1-—Dl. 
( = ( a ai ( a 
A contradiction. Therefore, we have that 
e 1 sera 
Pao eh. 
Da- =) 220-5 


Lemma 2.4.2 For a map M = (Xa,2,P) with o(M) faces and N = Il D;' Pi < 
po <-+++< pr, the arithmetic decomposition of the integer N, there asa voltage 
assignment 0 : Xa,g 4 Zn such that for VF € F(M), o(F) = pi if 6(M) = 0(mod2) 
or there exists a face Fy € F(M), o( F) = p, for VF € F(M)\ {Fo}, but o( Fo) = 1. 


Proof Assume that fi, fo,---, fn, whereyn = ¢(M), are the n faces of the map 
M. By the definition of voltage assignment, if 7, Gx or x,a@x appear on one face 
fi, 1 <i <n altogether, then they contribute to J(f;) only with 0(2)J7!(x) = 1z,,. 
Whence, not loss of generality, we only need to consider the voltage x;; on the 
common boundary among the face f; and f; for 1 < i,7 <n. Then the voltage 


assignment on the n faces are 


V(f1) = %12X%13°°* Lin, 


O( fa) = 121093 °°" Ln, 


Y(Sn) = LniXn2°**Un(n-1)- 


We wish to find an assignment on M which can enables us to get as many 
faces as possible with the voltage of order p,;. Not loss of generality, we can choose 


0P1(f,) =1z,, in the first. To make J?1( fz) = 1z,,, choose 223 = @}3,°**, Lan = Lin - 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 03 


If we have gotten v"(f;) = 1z, andi < nif n = O(mod2) ori < n—-1 if 
n = 1(mod2), we can choose that 

XL(i+1)(i+2) = Dy Li+1) (+3) = eG): 7+, XLG41)n = ie 
which also make J?"(fi41) = 1z,. 

Now if n = 0(mod2), this voltage assignment makes each face f;,1 <i <n 
satisfying that J?'(f;) = 1z,. But if n = 1(mod2), it only makes J?!(f;) = 1z,, for 
1<i<n-1, but 0(f,) =1z,. This completes the proof. b 

Now we can prove a result for the minimum genus of a fixed-free automorphism 


of a map. 


Theorem 2.4.1 Let M = (4 ,4,P) be a map and N = pj)---pi*,pi < po < 
< pr, be the arithmetic decomposition of the integer N. Then for any voltage 
assignment VU: Xa,3 — ZN, 
(i) if M is orientable, the minimum genus Gmin of the lifting map M° which 


admits an automorphism of order N, fixed-free on V(M°), is 


ye 


m€O(F(M)) P1 


(ii) if M is non-orientable, the minimum genus gi,,,, of the lifting map M® 


which admits an automorphism of order N, fixed-free on V(M°), is 


Gin = 2+ NEg(M) = 2420S. 


Proof (i) According to the Theorem 2.2.1, we know that 


1 


2—29(M") =N{(2—29(M))+ So (-14+ me 
méO(F(M)) 
Whence, 
2g(M*) =2+ N{Qg(M)-2+  (1-=)}. 
méO(F(M)) 


Applying the Lemma 2.4.1 and 2.4.2, we get that 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 54 


din = 14 N{g(M) 1+ (= [ED 


(ii) Similarly, by the Theorem 2.2.1, we know that 


1 
2—g(M®) =N{(2-9(M))+ YO (-1+=)} 
me€O(F(M)) on 
Whence, 
1 
g(M") =2+N{g(M)-2+ > (1-—)}. 
me€O(F(M)) me 
Applying the Lemma 2.4.1 and 2.4.2, we get that 
1. o(M 
Gin = 2+ NEg(M) —2420- SD 


4.2 The maximum order of an automorphism of a map 


For the maximum order of an automorphism of a map, we have the following 


result. 


Theorem 2.4.2 The maximum order Nmax of an automorphism g of an orientable 


map M of genus> 2 is 


Nmax < 2g(M) +1 


and the maximum order N/_,,, of a non-orientable map of genus> 3 is 


Nie = 9M) +1, 


where g(M) is the genus of the map M. 


Proof According to the Theorem 2.2.3, denote G =< g >, we get that 


xX(M)+ D7 (@.(9)1 + 182@))) = 1Glx(M/G), 


g€G,gAle 
where, ®;(g) = {F|F € F(M),F9 = F} and ©,(g) = {vjv € V(M), v9 = v}. If 
g # 14, direct calculation shows that ®-(g) = ®;/(g?) and ®,(g) = ®,(g?). Whence, 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold ays) 


» |8.(9)| = (GI — 1)1®.(9)| 


g€G,gAl1e 


and 


~  1®r(9)| = (GI - 1&9) 


g€G,gAlea 


Therefore, we get that 


x(M) + (IG] — 1]®.(9)| + UG] — Dl@r(g)| = |Glx(M/G) 


Whence, we have that 


x(M) — (1®.(9)1 + 1®r(9)I) = IGIx(M/G@) — ({®o(9) + [8 ¢(9)1)- 


If x(M/G) — (|®u(9)|+1@s(9)|) = Oi-e., x(M/G) = |®o(9)|+|®r(9)| 2 0, then 
we get that gi) <1 if M is orientable or g(M) < 2 if M is non-orientable. Con- 
tradicts to the assumption. Therefore, y(//G) — (|®,(g)| + |®-(g)|) 4 0. Whence, 
we get that 


__x(M) = (80) + 119) _ prey 
Gl = OMG) — Tso + FB y(ayh A Fi9)- 


Notice that |G], x(M) — ((6_(g)|-+1®/(9)|) and x(M/G) — ([®_(9)|+|&/(g)]) are in- 
tegers. We know that the function H(v, f; g) takes its maximum value at y(WV/G) — 
(|®.(g)| + |®¢(g)|) = —1 since x(M) <—1. But in this case, we get that 


IG] = |®,(g)| + |®(g)| —x(M@) = 1+ x(M/G) — x(™). 
We divide the discussion into to cases. 
Case 1 M is orientable. 


Since x(M/G) + 1 = (|®,(g)| + |®¢(g)|) > 0, we know that y(M/G) > —1. 
Whence, x(M/G) = 0 or 2. Therefore, we have that 


IG] = 1+ x(M/G) —x(M) < 3—x(M) = 29(M) + 1. 


That is, Nmae < 2g(M) +1. 


Chapter 2. On the Automorphisms of a Klein Surface and a s-Manifold 06 


Case 2 M is non-orientable. 


In this case, since y(M/G) > —1, we know that y(M/G) = —1,0,1 or 2. 
Whence, we have that 


Gla T+ x G) =x) <3= x) =a sk 


This completes the proof. L 
According to this theorem, we get the following result for the order of an auto- 
morphism of a Klein surface without boundary by the Theorem 1.2.7, which is even 


more better than the results already known. 


Corollary 2.4.1 The maximum order of an automorphism of a Riemann surface 
of genus> 2 is 2g(M) +1, and the maximum order of an automorphism of a non- 


orientable Klein surface of genus> 3 without boundary is g(M) + 1. 


The maximum order of an automorphism of a map can be also determined by 


its underlying graph, which is stated as follows. 


Theorem 2.4.3 Let M be a map underlying the graph G and Omar(M, g), Omax(G, 9) 
be the maximum order of orientation-preserving automorphism in AutM and in 
AutiG. Then 


Omar(M, g) <a One (Gs 9); 


and the equality hold for at least one map underlying the graph G. 


The proof of the Theorem 2.4.3 will be delayed to the next chapter after we 


prove the Theorem 3.1.1. By this theorem, we get the following interesting results. 


Corollary 2.4.2 The maximum order of an orientation-preserving automorphism of 


a complete map Ky,n > 3, is at most n. 


Corollary 2.4.3 The maximum order of an orientation-preserving automorphism of 
a plane tree T is at most |T|—1 and attains the upper bound only if the underlying 


tree 1s the star. 


Chapter 3 On the Automorphisms of a Graph on Sur- 
faces 


For determining the automorphisms of a map, an alternate approach is to con- 
sider the action of the semi-arc automorphism group of its underlying graph on 
the quadricells and to distinguish which is an automorphism of the map and which 
is not. This approach is first appeared in the reference [43] as an initial step for 
the enumeration of the non-equivalent embeddings of a graph on surfaces, and also 
important for enumeration unrooted maps underlying a graph on surfaces used in 
Chapter 4. 


§1. A necessary and sufficient condition for a group of a graph being 


that of a map 


Let [ = (V,E) be a connected graph. Its automorphism is denoted by AutI. 
Choose the base set X = E(I). Then its quadricells Y,,g is defined to be: 


Xap = U {5, ax, Bx, BaBx}, 


rex 
where, K = {1,a,3,a(} is the Klein 4- elements group. 
For Vg € AutI, define an induced action g|*=8 of g on X4, as follows. 


For Vx € Xa, if 9 = y, then define (ax)? = ay, (Gx)9 = By and (aBr)9 = 
aBy. 

Let M = (%a,6,P) be a map. According to the Theorem 1.2.5, for an auto- 
morphism g € AutM and glyym) : u > v, u,v € V(M), if ul = v, then call g 
an orientation-preserving automorphism. if uJ = v~!, then call g an orientation- 
reversing automorphism. For any g € AutM, it is obvious that g|p is orientation- 
preserving or orientation-reversing and the product of two orientation-preserving au- 
tomorphisms or orientation-reversing automorphisms is orientation-preserving, the 
product of an orientation-preserving automorphism with an orientation-reversing 


automorphism is ortentation-reversing. 


Chapter 3. On the Automorphisms of a Graph on Surfaces 508 


For a subgroup G x AutM, define G* ~X G being the orientation-preserving 
subgroup of G. Then the index of G* in G is 2. Assume the vertex v to be 
V = (£1, 22,°+*, Lo(v))(@Lp(x), +++, L2,2). Denote by < v > the cyclic group 
generated by v. Then we get the following property for the automorphisms of a 


map. 


Lemma 3.1.1 Let G <x AutM be an automorphism group of a map M. Then 
Vu Ee V(M), 
(i) if Vg € G,g is orientation-preserving, then Gy, X <u>, is a cyclic group; 
is Gy aS xk a 


Proof (i)Let M = (Xa,e,P). since for any Vg € G, g is orientation-preserving, 
we know for Vu € V(M),h € G,, v" = v. Assume the vertex 


US nig as * 5 ay OR iss Ol Away 4d) 


Then 


et toy pala | (Oleander: ax,)]" = (Fi B52 $y Roa) (ON) 6? OL2,0101). 


Therefore, if h(11) = re41,1 < k < p(v), then 


h = [(a1, 22,+++, Lp) (OLp(v), ULp(u)—1,***, @21)]* = v*. 


lf h( ei) = On, 6) eid = eS plo), then 
fe (tip tays 36h) (OL sah, Obeaain 5 ax,)|*a = ya, 


1 iie., h is not orientation- 


But if h = v*a, then we know that v? = v® = v7 
preserving. Whence, h = v*,1 < k < p(v), ie., each element in G, is the power of 
v. Assume € is the least power of elements in G,. Then G, =< v§ >X <u> isa 
cyclic group generated by v%. 


(ii)For Vg € Gy, v9 = v, Le., 


[(r1, T2,°7", Lp) (Ap, ALp-1," 7"; ax) |? > (x1, T2,° 7", Lp) (Ap, ALp-1," 7"; ax). 


Chapter 3. On the Automorphisms of a Graph on Surfaces 09 


Similar to the proof of (i), we know there exists an integer s,1 < s < p, such 


that g = v* or g = via. Whence, ge<vu>orge<vu>a,ie., 
g g 
G, <x<vu>x<a>. h 


Lemma 3.1.2 Let [ be a connected graph. If G x Autl, and Vu € V(L),Gy x < 
vu>x <a>, then the action of G on Xq,g 18 fixed-free. 


Proof Choose a quadricell x € %,3. We prove that G,; = {1c}. In fact, if 
g € Gz, then x9 = x. Particularly, the incident vertex u is stable under the action 


of g, i.e., ul = u. assume 


uUu= (x, Yi 70"; Yp(u)—1) (ax, WY p(u)—1s* "5 ay), 


then since G, <x <u>x <a>, we get that 


r= x, yi = Yi 5 You) = Yo(u)-1 


and 


(ax)? = An, (ay1)9 = AYi,°°"; (QYp(u)—1)? = AYp(u)-1) 


that is, for any quadricell e,, incident with the vertex u, ef = e,. According to the 


definition of the induced action Aut on ¥.,3, we know that 


(Gx)? = Px, (By1)9 = Py, ey (BYo(uy-1)? = Out = 


and 


(aBa)? = apex, (aby)? = apy, as (aBYp(u)-1)9 = UBYo(u)-1- 


Whence, for any quadricell y € 4,3, assume the incident vertex of y is w, 
then by the connectivity of the graph [, we know that there is a path P(u,w) = 
uvyv2:--u,w in T connecting the vertex wu andw. Not loss of generality, we assume 
that By, is incident with the vertex v,. Since (Gy,)9 = Gy, and Gy, Xx <u> x < 


a >, we know that for any quadricell e,, incident with the vertex v1, e%, = €y,. 


Chapter 3. On the Automorphisms of a Graph on Surfaces 60 


Similarly, if a quadricell e,, incident with the vertex v; is stable under the action 
of g, i.e., (€v,)9 = €y,, then we can prove that any quadricell e,,,, incident with the 
vertex U;,1 is stable under the action of g. This process can be well done until we 
arrive the vertex w. Therefore, we can get that any quadricell e,, incident with the 
vertex w is stable under the action of g. Particularly, we have that y? = y. 

Therefore, we get that g = 1g. Whence,G, = {1c}. h 

Now we prove a necessary and sufficient condition for a subgroup of a graph 


being an automorphism group of a map underlying this graph. 


Theorem 3.1.1 Let I be a connected graph. IfG x AutI’, then G is an auto- 
morphism group of a map underlying the graph T iff for Yu € V(L), the stabler 
G,x~<vu>x<a>. 


Proof According to the Lemma 3.1.1(zi), the condition of the Theorem 3.1.1 is 
necessary. Now we prove its sufficiency. 

By the Lemma 3.1.2, we know that the action of G on ¥q,g is fixed-free, i.e., 
forVr € Xa, |G:| = 1. Whence, the length of orbit of « under the action G is 
|x@| = |G,||v°| = |G, ie., for Vr € Xq.¢, the length of x under the action of G is 
|G|. 

Assume that there are s orbits O,O2,---,O; of G action on 7£ V(T), where, 
O; = {t1, U2,+++, Ue}, Oo = {U1, v2, +++, Vi},-+ ;Os = {W1, We,-++, We}. We construct 
the conjugatcy permutation pair for every vertex in the graph T’ such that they 
product P is stable under the action of G. 

Notice that for Vu € V(L), since |G| = |G.,||w@|, we know that [k,1,---,¢]| |G]. 

In the first, we determine the conjugate permutation pairs for each vertex 
in the orbit O,. Choose any vertex u,; € Oj, assume that the stabler G,, is 


m1 

{le 91, 9291,°°*; TI] Gm-i}, where, m = |G,,| and the quadricells incident with 
i=l 

vertex ui is N(uz) in the graph I. We arrange the elements in N(uz) as follows. 


Choose a quadricell uf € N(u,). We use G,, action on uf and auf, respec- 
q 1 1 1 1 


m—-1 
tively. Then we get the quadricell set A; = {uf,gi(u$),---, I] Qm—i(uf)} and 
i=l 


m—1 

aA; = {auf,agi(uf),---,@ T] gm—i(ut{)}. By the definition of the action of an 
i=1 

automorphism of a graph on its quadricells we know that A;()aA; = 9. Arrange 


m1 
the elements in A, as A; = uf, gi(ut),---, IL Gm—i(ut). 
i=l 


Chapter 3. On the Automorphisms of a Graph on Surfaces 61 


If N(ur) \ A, UaA; = 9, then the arrangement of elements in N(u1) is A. 
If N(ur) \ AiUaA, 4 0, choose a quadricell uf € N(ur) \ AiUa@A,. Similarly, 


m—1 
using the group G,,, acts on u?, we get that Ay = {u®, g:(ue),---, I Jm—i(u?)} and 


m1 
aA, = {au?,ag(ue),--+,a T Jm—i(ue)}. Arrange the elements in A; U A» as 
See m1 
Ai (J A2 = = wt, G1 (Uy), 2a al Imi (a) ue gi (u’), it Imi (u?). 


w= 1 


If N(uz) \ (A, UA2U @A; UaA2) = 0, then the arrangement of elements in 

A, U Az is Ai J Ao. Otherwise, N(uy) \ (A, U 42 UaA; UaAz) 4 0. We can choose 

another quadricell uf € N(ur) \ (A, U A2U aA; UaA2). Generally, If we have got- 

ten the quadricell sets A,, Ag,---,A;,1 <r < 2k, and the arrangement of ele- 

ment in them is Ai) A2LJ---LJ Ap, if N(us) \ (A1U A2U---U 4A, Ar Ua Ag U 

--UaA,) 4 0, then we can choose an element u? € N(uy)\(Ay U AoU---UA,UaA; 
UaA2U--:-UaA,) and define the quadricell set 


m—-1 
Ayat = ful, 91 (a); peg Gmc) 
i=l 
Ary = faut, agi(uf),---,a inf Gm—i(ut)} 
and the arrangement of elements in A,.., is 
———> ™m— 
Ap = ut n (uf), Tm 


Define the arrangement of elements in iV) A, to be 
j=l 


r+l 
U A; a =a Ay Asa 


Whence, 


k 


N(t) a (U A;) Ula 


q=1 


Aj) 


a. 
Co» 


and A; is obtained by the action of the stabler G,, on uf. At the same time, the 
— 
k 


arrangement of elements in the subset U A,; of N (u1) to be |) Aj. 
j= j=l 


Chapter 3. On the Automorphisms of a Graph on Surfaces 


62 
Define the conjugatcy permutation pair of the vertex u; to be 


where, 


Our = (C) (aC ta), 


m—-1 m-1 m—-1 
C= (uf, Uz, *, ut; gi(ut), g1(u7),° Gi ts Ss IL (@d. I]@ a) [[ @)) 
i=1 i=1 i=1 


For any vertex u; € O,,1 <i <k, assume that h(u,) = u;, where h € G, then 
we define the conjugatcy permutation pair 0,, of the vertex u; to be 


Ou; = Ou, = (C")(aCa™"). 
Since QO, is an orbit of the action G on V(I), then we have that 
k . k 
i=1 i=1 
Similarly, we can define the conjugatcy permutation pairs 0,,, Qv., 
Ow ,***, Ow, Of vertices in the orbits O2,---,O;. We also have that 


“4 Quy? 


“* 5) Ow, 


(II Ov,)° 


l 
[I &.- 
41 


oul Og 


Now define the permutation 


I| 
i. 
> 
& 


P= (II Ou;) x (L] 20.) alia. (L] ou.), 
that 


Then since O;, O2,---,O; are the orbits of V(I) under the action of G, we get 


Chapter 3. On the Automorphisms of a Graph on Surfaces 63 


Po = (Pou)? x (on)? x-- x Lon) 


(II Ou; ) x (II Ov, ) Xr X (II Des =P. 


Whence, if we define the map M = (4,,3,P), then G is an automorphism of 
the map M. h 


For the orientation-preserving automorphism, we have the following result. 


Theorem 3.1.2 Let T be a connected graph. If G x AutI, then G is an orientation- 
preserving automorphism group of a map underlying the graph T iff for Vu € V(L), 
the stabler G, < <vu> is a cyclic group. 


Proof According to the Lemma 3.1.1(i), we know the necessary. Notice the ap- 
proach of construction the conjugatcy permutation pair in the proof of the Theorem 
3.1.1. We know that G is also an orientation-preserving automorphism group of the 
map M. h 


According to the Theorem 3.1.2, we can prove the Theorem 2.4.3 now. 


The Proof of the Theorem 2.4.3 


Since every subgroup of a cyclic group is also a cyclic group, we know that any 
cyclic orientation-preserving automorphism group of the graph T is an orientation- 
preserving automorphism group of a map underlying the graph I by the Theorem 
3.1.2. Whence, we get that 


Oper MG): = Omis(G.g). —t 


Corollary 3.1.1 For any positive integer n, there exists a vertex transitive map 
M underlying a circultant such that Z,, is an ortentation-preserving automorphism 


group of the map M. 


Remark 3.1.1 Gardiner et al proved in [20] that if add an additional condition , 
i.e, G is transitive on the vertices in I’, then there is a regular map underlying the 


graph T. 


Chapter 3. On the Automorphisms of a Graph on Surfaces 64 


§2. The automorphisms of a complete graph on surfaces 


A map is called a complete map if its underlying graph is a complete graph. 
For a connected graph I’, the notations €°(f),E% (I) and €4(I) denote the embed- 
dings of I on the orientable surfaces, non-orientable surfaces and locally surfaces, 


respectively. For Ve = (u,v) € E(L), its quadricell Ke = {e, ae, Ge,aBe} can be 





represented by Ke = {u’t,u’,v%t, vu" }. 
Let K,, be a complete graph of order n. Label its vertices by integers 1, 2, ...,n. 
Then its edge set is {ij|1 <i,7 <n,if# jij = ji}, and 


Hep h,) Ste 21a ee POL 21S eg ee a}. 


a= II (7,47), 


1<t,j<niFg 
j= Il (9+, i+) (97, 077). 
1<i,j<niAj 
We determine all the automorphisms of complete maps of order n and give they 
concrete representation in this section. 
First, we need some useful lemmas for an automorphism of a map induced by 


an automorphism of its underlying graph. 


Lemma 3.2.1 Let I be a connected graph and g € Autl’. If there is a map M € 
E(I') such that the induced action g* € AutM, then for V(u,v), (x,y) € E(L), 


[U9(w), 19(v)] = [19 (x), 19(y)| = constant, 


where, I9(w) denotes the length of the cycle containing the vertex w in the cycle 


decomposition of g. 


Proof According to the Lemma 2.2.1, we know that the length of a quadricell 
u’t or u”~ under the action g* is {/9(u), 19(v)]. Since g* is an automorphism of map, 


therefore, g* is semi-regular. Whence, we get that 


[29(w), 19(v)] = [19 (x), 4 (y)| = constant. h 


Chapter 3. On the Automorphisms of a Graph on Surfaces 65 


Now we consider conditions for an induced automorphism of a map by an 


automorphism of graph to be an orientation-reversing automorphism of a map. 


Lemma 3.2.2 If €a is an automorphism of a map, then a = aé. 


Proof Since €a is an automorphism of a map, we know that 


(Saja = alfa). 
That is, £a = a. h 
Lemma 3.2.3 If € is an automorphism of map M = (Xa,9,P), then €a is semi- 
regular on Xq,3 with order o(&) if o(€) = O(mod2) and 20(€) if o(€) = 1(mod2). 


Proof Since € is an automorphism of map by the Lemma 3.2.2, we know that 


the cycle decomposition of € can be represented by 
f= [[ (1, 2, oe ‘9 h_) (OL); AT2,°**, AL), 
k 
where, [], denotes the product of disjoint cycles with length k = o(&). 


Therefore, if k = 0(mod2), we get that 


Ea = [[(j@. L2,%3,°°", Lp) 
k 


and if k = 1(mod2), we get that 


Ea = [Ij OX], U3,° °°, UR, AL], VQ,AV3,°°°, AL;). 
2k 
Whence, € is semi-regular acting on Vy,3. h 


Now we can prove the following result for orientation-reversing automorphisms 


of a map. 


Lemma 3.2.4 For a connected graph T, let K be all automorphisms in Aut! whose 
extending action on X43, X = E(T), are automorphisms of maps underlying the 
graph T. Then for VE € K, o(&*) > 2, Ea € K if and only if o(&*) = 0(mod2). 


Proof Notice that by the Lemma 3.2.3, if €* is an automorphism of map with 


underlying graph I’, then €*a is semi-regular acting on %y,,. 


Chapter 3. On the Automorphisms of a Graph on Surfaces 66 


Assume €* is an automorphism of map M = (%a,g,P). Without loss of gener- 


ality, we assume that 








P =C,0y---Cp, 
where,C; = (%i1, Ui2,-++,2ij,) is a cycle in the decomposition of €|yir) and xy = 
{(e" ,e,---, e) (ae, aett,---, ae'”)} and. 
Elza) a (en, €12,°°°, €5, )(€a1, €22,°°", C255) ene (en, €12,°°", Cts, )- 
and 
€* = C(aC™'a), 
where, Le — (eu, €12,°°°, €5,) (E21, €22,°°", C255) ae (en, €12,° °°", Cls,): Now since & is 
an automorphism of map, we get that 5; = so =---=s,;=0(&*) =s. 
If o(€*) = 0(mod2), define a map M* = (%q,3, P*), where, 
P* = C105 -+-Ch, 
where, Cf = (2},2ip,°° ai); Gi = {leh ej. 7" ej, ) (wen, QE js. “++, €%)} and 


CF; = Cpg. Take ef; = pq if q = 1(mod2) and e7; = ep, if q = 0(mod2). Then 
we get that MS* = M. 

Now if o(€*) = 1(mod2), by the Lemma 3.2.3, o(€*a) = 20(€*). Therefore, any 
chosen quadricells (e’!, e’,---,e"’) adjacent to the vertex xv for i = 1,2,---,n, 
where, n = |I'|, the resultant map M is unstable under the action of €a. Whence, 
€a is not an automorphism of one map with underlying graph I. h 

Now we determine all automorphisms of a complete map underlying a graph 
K,, by applying the previous results. Recall that the automorphism group of the 


graph K,, is just the symmetry group of degree n, that is, AutK, = Sy. 
Theorem 3.2.1 All orientation-preserving automorphisms of non-orientable com- 
plete maps of order> 4 are extended actions of elements in 


€ E n-1 


[s#]? [less ]’ 
and all orientation-reversing automorphisms of non-orientable complete maps of 


order> 4 are extended actions of elements in 


Chapter 3. On the Automorphisms of a Graph on Surfaces 67 


aێ aێ En 1,9), 


[(2s) 35]? [(28) 35]? 


where, Eg denotes the conjugatcy class containing element @ in the symmetry group 
Sn 


Proof First, we prove that the induced permutation €* on a complete map of 
order n by an element € € S,, is an cyclic order-preserving automorphism of non- 


orientable map, if, and only if, 


g = E43 UE, a] 
Assume the cycle index of € is [{1*!,2",...,n*"]. If there exist two integers 
ki,k; A 0, and 2,7 > 2,7 ~€ j, then in the cycle decomposition of € , there are two 


cycles 


(U1, Ua,..., Us) and (v4, Ua, ..., Uj). 
Since 
[I (ua), U8 (u2)} =i and [IF (v4), U8 (v2)] = J 


and i # j, we know that €* is not an automorphism of embedding by the Lemma 
2.5. Whence, the cycle index of € must be the form of [1*, s!]. 

Now if k > 2, let (uw), (v) be two cycles of length 1 in the cycle decomposition 
of €. By the Lemma 2.5, we know that 


f(u), E(0)] = 1. 
If there is a cycle (w,...) in the cycle decomposition of € whose length greater 


or equal to two, we get that 


[UF (u), &(w)] = [1, Bw] = FF (w). 


According to the Lemma 3.2.1, we get that [§(w) = 1, a contradiction. There- 


fore, the cycle index of € must be the forms of [s!] or [1,s']. Whence,sl = n or 





sl+1=n. Calculation shows that 1 = 4 or 1 = a That is, the cycle index of € 
no-1 


is one of the following three types [1”], [1,s~= ] and [s*] for some integer s . 


Chapter 3. On the Automorphisms of a Graph on Surfaces 68 


Now we only need to prove that for each element € in a aay and E53] , there 
exists an non-orientable complete map M of order n with the induced permutation 
&* being its cyclic order-preserving automorphism of surface. The discussion are 


divided into two cases. 


Case 1 EE Ey 


32] 
Assume the cycle decomposition of € being € = (a,b,---,c)--+- (a, y,-++, 2) +++ (u,v, 
--+,w), where, the length of each cycle isk, and 1 < a,b,-++,6,2,Y,++°,2,U,U,7°°,W< 


n . In this case, we can construct a non-orientable complete map M, = (X28) P1) 


as follows. 
Hep =F 1 sij smile :1<ij sni4 j}, 
Pi = I (C(x))(aC(x)~*a), 
LE{A,b,-,0,25,2,Y,701,2,U,V, 7, } 
where, 
C(x) me ar Fae oe Re Aone ee, ae ae 


aC(«)*a = (a i A a pene, eke): 
It is clear that MS” = M,. Therefore, €* is an cyclic order-preserving automor- 


phism of the map M;. 


Case 2 Ee Ey nel 





We assume the cycle decomposition of € being 


CGO ik OC) Ral te Yites 2) aso) E), 


where, the length of each cycle is k beside the final cycle, and 1 < a, b...c, 2, y..., z, 
U,U,..,w,t <n. In this case, we construct a non-orientable complete map Mz = 
(42 3, P2) as follows. 


Chapter 3. On the Automorphisms of a Graph on Surfaces 69 


Agel ELS Sas ae a So 

















Po = (A)(aA™") II (C(x))(aC(x)~*a), 
LE{A,D,...,C,...,0,Y,++-Z,UsV,---5w } 
where, 
BOS et RE ee A eet) 
and 
OAT ds oath DU gs nat kk abe yea ) 
and 
CaS", ae Dae ae Pare see oa ia ert) 
and 
OY ec aa cae SEN ce 


It is also clear that MS" = Mp). Therefore, €* is an automorphism of a map M2 


Now we consider the case of orientation-reversing automorphism of a complete 
map. According to the Lemma 3.2.4, we know that an element €a, where, € € S,, 


is an orientation-reversing automorphism of a complete map, only if, 


cee 


Our discussion is divided into two parts. 


nm—ny1 . 


[kh ,(2k) ak | 





Case 3 n=n 


Without loss of generality, we can assume the cycle decomposition of € has the 


following form in this case. 


€ = (1,2,-+-,k)(R+1, B42, +++, 2k) (m—k+1,n—k+2,---,7). 


Chapter 3. On the Automorphisms of a Graph on Surfaces 70 


Subcase 3.1 k = 1(mod2) and k > 1 


According to the Lemma 3.2.4, we know that €*a is not an automorphism of 


map since o(€*) = k = 1(mod2). 
Subcase 3.2 k = 0(mod2) 


Construct a non-orientable map M3; = (¥}4,P3), where X? = E(K,,) and 


P= [I (C@)(eC@a), 


i€{1,2,--,n} 
where, if i = 1(mod2), then 
(gl + pk+1+ -n—k+1+ 2+ -n—k+2+ “1 kt pQk+ n+ 
Cay= 52 got gt 52 pit yt gor PS get poe Tt 52 go yt Ms 
La nes te 2k- ck -k+1— 
GC). Gj a pte he et ) 
and if 7 = 0(mod2), then 
Vo ¢el— -k+1— n—k+1— .2— n—k+2— “1 “k— Qk 2 
C(t) = (i 52 go Tat 52 Ree ae yar TRIG AG eer 52 3 Pagel iF 
Rs pie eek Okt okt bla 
GO) SOS Rg eee eee ). 


Where, i’* denotes the empty position, for example, (2', 27*, 23,24, 2°) = (2', 23,24, 2°). 


It is clear that P3* = P3, that is, €a is an automorphism of map M3. 
Case 4 ny An 


Without loss of generality, we can assume that 


g = (G2 ah) Rae 25m) ee See Ly ip Re Os Soy) 
x (ny t1,n + 2,---,m, + 2k) (ny + 2k 4+1,---,2, + 4k)---(n — 2k +1,---,n) 


Subcase 4.1 k = 0(mod2) 


Chapter 3. On the Automorphisms of a Graph on Surfaces 71 


Consider the orbits of 12+ and n; + 2k + 1'* under the action of < Ea >, we 
get that 


lorb((17*)<6°7)| = k 


and 


lorb(((ny + 2k + Lyon) 8) = 2k. 
Contradicts to the Lemma 3.2.1. 
Subcase 4.2 k = 1(mod2) 


In this case, if k £1, then k > 3. Similar to the discussion of the Subcase 3.1, 


we know that €a is not an automorphism of complete map. Whence, k = 1 and 


EE Etim 272). 


Without loss of generality, assume that 


€ = (1)(2) eg (ni) (4 + 1,n4 + 2)(n4 + 3, M1 + 4) ae (ny + ng —- 1,n4 +9). 


If ng > 2, and there exists a map M = (%.,8,P), assume the vertex v; in M 
being 


U= (Gigca plist oat eee | laced flin- wae ie) 


where, 11; € {+2, —2, +3, —3,---,+n,—n} and hh, Ah; ift #7. 
Then we get that 


(v,)&° = Gu pe aoe piin-) (yaa, pant re Per) é U1L- 


Whence, €a is not an automorphism of map M. A contradiction. 
Therefore, no = 1. Similarly, we can also get that ny = 2. Whence, € = 
(1)(2)(34) and n = 4. We construct a stable non-orientable map M, under the 


action of €a as follows. 


Ms, — (Ae a: Py) 


Chapter 3. On the Automorphisms of a Graph on Surfaces 72 


where, 





Pi = Ger ere) Orne ger Det gh eet eet Art At der) 
a sane gs ae) | erry” |r eS aa |e a a 





Therefore, all orientation-preserving automorphisms of non-orientable complete 
maps are extended actions of elements in 


€ E n-1 


[es “Weta ] 





and all orientation-reversing automorphisms of non-orientable complete maps are 


extended actions of elements in 


aێ z aێ 4 Eq 1,9). 


This completes the proof. h 

According to the Rotation Embedding Scheme for orientable embedding of 
a graph, First presented by Heffter in 1891 and formalized by Edmonds in [17], 
each orientable complete map is just the case of eliminating the sign + and - in 
our representation for complete map. Whence,we have the following result for an 


automorphism of orientable surfaces, which is similar to the Theorem 3.2.1. 


Theorem 3.2.2 All orientation-preserving automorphisms of orientable complete 
maps of order> 4 are extended actions of elements in 


€ E n-1 


[ss}) “ts 





] 
and all orientation-reversing automorphisms of orientable complete maps of order> 


4 are extended actions of elements in 


a€é a€ 


e®p  Cay&p Cts 


where,E€g denotes the conjugatcy class containing 0 in Si. 


Proof The proof is similar to that of the Theorem 3.2.1. For completion, we only 
need to construct orientable maps M?,i = 1,2,3,4, to replace the non-orientable 


maps M;,7 = 1,2,3,4 in the proof of the Theorem 3.2.1. 


Chapter 3. On the Automorphisms of a Graph on Surfaces 73 


In fact, for orientation-preserving case, we only need to take M?, MY to be 
the resultant maps eliminating the sign + and - in M,, M2 constructed in the proof 
of the Theorem 3.2.1. 


For the orientation-reversing case, we take M? = (E(Ky)a,g, PY) with 


¢€{1,2,---,n} 
where, if i = 1(mod2), then 
— (gl k+l ‘n—k+1 2 “‘n—k+2 o* +k 2k n 
Ca) =(t,1 ’ »o 2, ’ ’ »b >t, ’ yo ); 
and if 7 = 0(mod2), then 
of -1 +k+1 -n—k+1 2 nm—k+2 +h +k 2k n\—1 
Ci) =(,1 yityt pb ttt, 0 pitty b grrr, t et ear ae) ’ 


where 7* denotes the empty position and M? = (E(K4)o,g, Pa) with 


P4 aa (ie Vee 13) 2 hg 2") (35 3; 3) (4s 4, 4°). 


It can be shown that (M?)** = M® for i = 1,2,3 and 4. h 


§3. The automorphisms of a semi-regular graph on surfaces 


A graph is called a semi-regular graph if it is simple and its automorphism 
group action on its ordered pair of adjacent vertices is fixed-free, which is considered 
in [43], [50] for enumeration its non-equivalent embeddings on surfaces. A map 
underlying a semi-regular graph is called a semi-regular map. We determine all 
automorphisms of maps underlying a semi-regular graph in this section. 

Comparing with the Theorem 3.1.2, we get a necessary and sufficient condition 


for an automorphism of a graph being that of a map. 


Theorem 3.3.1 For a connected graphT, an automorphism € € AutT is an orientation- 
preserving automorphism of a non-orientable map underlying the graph T aff € is 


semi-regular acting on its ordered pairs of adjacent vertices. 


Chapter 3. On the Automorphisms of a Graph on Surfaces 74 


Proof According to the Lemma 2.2.1, if € € AutI is an orientation-preserving 
automorphism of a map M underlying graph I’, then € is semi-regular acting on its 
ordered pairs of adjacent vertices. 

Now assume that € € AutI is semi-regular acting on its ordered pairs of adja- 
cent vertices. Denote by €|ycr), Ele), the action of € on V(I) and on its ordered 


pairs of adjacent vertices,respectively. By the given condition, we can assume that 


Elva) = (@,8,-++,€) +++ (g,h,- ++, k++ (2, y,° ++, 2) 


and 


Ela), = Cr+ Cis Cm, 
where, s,|C(a)| = --- = s,|C(g)| = --: = s,|C(x)|, and C(g) denotes the cycle 


containing g in €|ycr) and 
1 2,1 1 2 22 2 
Ci = (a 1b 77,0 ,@ 1b pry See ae are a oe 


CH = ae etree ace cots eee eee eae a 
Now for Vé,€ € AutI. We construct a stable map M = (%.,3,P) under the 


action of € as follows. 


X = E(T) 


and 


P= [I I] (G)(ec;"). 


geTy reC(g) 


Assume that u = €/(g), and 


Nr(g) = 19° 30 "ae ce id 2 


Chapter 3. On the Automorphisms of a Graph on Surfaces 75 


Obviously, all degrees of vertices in C(g) are same. Notices that €|y,(9) is 
circular acting on Np(g) by the Theorem 3.1.2. Whence, it is semi-regular acting 


on Np(g). Without loss of generality, we can assume that 


E| pcg) = (Oss G?: aie) Gg, gos, ney gr") ras (gine, quent, PS ig?) 


where, 1 = ks. Choose 


= Z1+ 7%stit Zk— + p22+ p%s+2+ Zst 22 Zket 
Cy = (9 1g Re ul Ler @W 1g pete 59 Get ag 2 


Then, 


Ge = (ger: ie vee, grk-Ystit geen. ae vee get are. vee, phe) 


where, 


att = EF(g**), 


for y= 1,2; +.ks; and 


Zs41t + 
’ 


aC, = (ax *,axr sa, Cpe Det1t quay ype ~ os, cug*het), 


Immediately, we get that M$ = €Mé-! = M by this construction. Whence, € 
is an orientation-preserving automorphism of the map M. h 

By the Rotation Embedding Scheme, eliminating @ on each quadricell in Tutte’s 
representation of an embedding induces an orientable embedding with the same 
underlying graph. Since an automorphism of an embedding is commutative with a 
and G3, we get the following result for the orientable-preserving automorphisms of 


the orientable maps underlying a semi-regular graph. 


Theorem 3.3.2 If T is a connected semi-regular graph, then for VE € AutI’, € is an 


orientation-preserving automorphism of orientable maps underlying the graph TI. 


According to the Theorem 3.3.1 and 3.3.2, if I is semi-regular, i.e., each au- 


tomorphism acting on the ordered pairs of adjacent vertices in I is fixed-free, then 


Chapter 3. On the Automorphisms of a Graph on Surfaces 76 


every automorphism of the graph IT is an orientation-preserving automorphism of 
orientable maps and non-orientable maps underlying the graph I’. We restated this 


result as the following. 


Theorem 3.3.3 Jf TI is a connected semi-regular graph, then for VE € Autl, € 
is an orientation-preserving automorphism of orientable maps and non-orientable 


maps underlying the graphT. 


Notice that if ¢* is an orientation-reversing automorphisms of a map, then ¢*a 
is an orientation-preserving automorphism of the same map. By the Lemma 3.2.4, 
if 7 is an automorphism of maps underlying a graph I’, then Ta is an automorphism 
of maps underlying this graph if and only if r = O(mod2). Whence, we have the 


following result for the automorphisms of maps underlying a semi-regular graph 


Theorem 3.3.4 Let [ be a semi-regular graph. Then all the automorphisms of 


orientable maps underlying the graph T are 


g\*~8 and ah|*8,g,h € Aut with h = 0(mod2). 


and all the automorphisms of non-orientable maps underlying the graph T are also 


g|*28 and ah|*=,g9,h € Aut with h = 0(mod2). 


Theorem 3.3.4 will be used in the Chapter 4 for the enumeration of unrooted 


maps on surfaces underlying a semi-regular graph. 


§4. The automorphisms of one face maps 


There is a well-know result for the automorphisms of a map and its dual in 
topological graph theory, i.e., the automorphism group of a map is same as its dual. 
Therefore, for determining the automorphisms of one face maps, we can determine 
them by the automorphisms of a bouquet B,, on surfaces. 

A map underlying a graph B,,n > 1 has the form B,, = (X38, Pn) with X = 
E(B,,) = {€1, €2,°++,@n} and 


Chapter 3. On the Automorphisms of a Graph on Surfaces 77 


Pa (big Bay 2 5 Cag) (OL AL an; ¢ 5 La) 


where, 7; € X, 0X or aZX and satisfying the condition (C7) and (Ci%z) in the Section 
2.2 of Chapter 1. For a given bouquet B, with n edges, its semi-arc automorphism 


group is 


Aut1 By, = S,[So]. 
Form group theory, we know that each element in S',[S2] can be represented by 
(g; hi, ho,-++, hn) with g € S, and h; € Sy = {1,a(0} for i = 1,2,---,n. The action 
of (g; hi, ho,-++,hn) on a map B,, underlying a graph B,, by the following rule: 
af © S es; Es, Bei, afe;}, then (9; hy, ho, ae: hin) (2) _ g(hi(x)). 
For example, ifh; = a, then,(g; hy, hea,-+-, Rn)(e1) = a3g(e1), (9; hi, ha,---, Rn) (er) 


= Bg(e1), (9; ha, ha,-++, hn)(Ge1) = ag(er) and (g; hi, he, +++, Mn)(aBe1) = ger). 
The following result for automorphisms of a map underlying a graph B,, is 


obvious. 


Lemma 3.4.1 Let (g; hi, ha,-++,hn) be an automorphism of a map B,, underlying a 
graph B,. Then 


(9; hi, ho, Bes hn) = (x1, LQ, +055 Pen)" 


and if (g; hi, he,-++,hn)a is an automorphism of a map B,,, then 


(93 ii, Ray ++ +, Mn)or = (a1, £2,°+*,Lan)* 
for some integer k,1 <k <n. Where, x; € {€1,€2,---,en},i = 1,2,---,2n and 
Ee ap yt x). 
Analyzing the structure of elements in the group S;,[S2], we get the automor- 


phisms of maps underlying a graph B, by the Theorem 3.3.1 and 3.3.2 as follows. 


Theorem 3.4.1 Let B,, be a bouquet with n edges 1,2,---,n. Then the automor- 
phisms (g; hy, h2,---,hn) of orientable maps underlying a By,n > 1, are respective 


(Ol) gE ELE, hy =1,0=1,2,---,n; 


Chapter 3. On the Automorphisms of a Graph on Surfaces 78 


n/k 
(O02) gé E ae) and if g = HI (1, t2,- te) Where 4 E41 nt nl k= 


O(mod2), then ee = (ap a= 19... ee and, Ng. fof 9-2 





ii _ . (n—2ks)/2k 
(O03) gE€ aa and if g= I] (41, 225° “iy TN. (epi aus 2 ees.) 
[k25,(2k) i=l j=l 
where 1;,e;, € {1,2,--- ae then he = Wyott = leet ig SL for be 
2 and h;,=1 fort =1,2,---,2k 
and the automorphisms (g; hy, he,-++,hn) of non-orientable maps underlying a B,,n 


> 1, are respective 
(N1) GEER, hy =1,0=1,2,---,n; 


u 


(N2) ge Endy and if g = II] (t1,%2,---t), where i; € {1,2,---,n},n/k = 
=1 
O(mod2), then h;, = (1, a), (1, 2) math at least one hi, (1, 8),1 = 1,2,---, Bandh, = 


1 for j 2 2; 
2s (n—2ks) /2k 
(V3) gé ae as and if g= l I] (415425 °- -ip) au (Cp ceryertnges 
WHEE 45,05, {1.2 ne then hiye= “(1 @8), (1,8) with at least one hi, = 
(2) = 123 shy = 1 ford ao and tee = be fort = 1, 224285 2k, 


where, Eg denotes the conjugacy class in the symmetry group S, containing the 





element 0. 


Proof By the structure of the group S;,,[S9], it is clear that the elements in the 
cases (7), (iz) and (ii) are its all semi-regular elements. We only need to construct 
an orientable or non-orientable map B,, = (1,3, Pn) underlying B,, stable under the 


action of an element in each case. 


n/k 
Gy = TH (1, 425 ++ te) and A;= 1,7 = 1, 2,-++n, where 7,-€ {1,2,-++;n}. 


Choose 
n/k 


Xo.8 = U Kit, 42, _ “i lehs 


i=1 


where K = {1,a,3,a(} and 


Ph = Ci(aCy*a7") 


with 


Chapter 3. On the Automorphisms of a Graph on Surfaces 79 


nr nm nm 
C} = ( dis 21,7075 (7 )1, B11, A821, ++, a8(F 1, La, 205° +5 (5 Jas 
nm nm nm 
aBlo, aB2, aes cB (a, eee) Ly, 2K; sea) (F)is On Lay, aBle, say cB (+ )e)- 


Then the map B), = (42,g,P,,) is an orientable map underlying the graph B,, and 
stable under the action of (g; hi, ha,-++, An). 


For the non-orientable case, we can chose 
n n n 
C= ( dig iy ipo liy 2 in ty BC) gla, 29,8 <5 (=); 
k; k; k; 
n n n 
Bla, (2x, : “A(z Jas i rte Os (5 is Blas Ble, - BCT )e): 
Then the map B) = (4j,g,P,,) is a non-orientable map underlying the graph B,, 


and stable under the action of (g; hy, ho,--+, An). 


n/k 
(zi) g= I] (a, %2,- apy hj = (1, 8) or (1,a8),1 = E25 7, Mn, = = O(mod2), 


where 7; € fi Do. + nh. 
If hi, = (1,8) fori = 1,2,---,? and h;, = 1 for t > 2. Then 
n/k 


(9; hy, ho, eae hn) — [[G. aia, a Bip, aBiy, to, aks) ip). 


i=1 


Similar to the case (i), we take 42, = Vj, and 


P= CylaCs a") 


with 


Cy = ( li, 21-5 (F)1, @Bl2, 0822, ++, 08(F)2, 0B 1p, 082, 
nm nm nm nm 
UBL Vis HPL 1, O12, > +>, /B(>)1, La, 2a,-+ +5 (Jaye +s Tes 2k o 5 CF )a)- 


Then the map B? = (¥%5,P2) is an orientable map underlying the graph B,, and 
stable under the action of (g;h1,h2,---,hn). For the non-orientable case, the con- 
struction is similar. It only need to replace each element afi; by (7; in the con- 


struction of the orientable case if h;, = (1, 3). 


Chapter 3. On the Automorphisms of a Graph on Surfaces 80 


2s (n—2ks)/2k 


(vit) {= TT (#15 #25 ++ >t) I (Cia Cia? 5) and hi, = (1, a8), i= 


et 
1 ehh SS lord 22 Gnd tie = Port SS OK 


In this case, we know that 


8 (n—2ks)/2k 
(9; hy, ha, +++, Rn) = [[ 4, Bia, +++ a Bix, wBi1, iz, +++, ix) Il (Gp hOage yes). 
i=l j=l 


Denote by p the number (n — 2ks)/2k. We construct an orientable map B3 = 
(42 5, P?) underlying B,, stable under the action of (g; hy, h2,--+, hn) as follows. 
Take 43.4 = Vj and 


P3 = C3(aC310"') 


with 


Cz = ( 1, pein Bis ees COs? * ty Cp pO laa 25, OSs, 


Elo, €20,°° "5 Epa," * -, aP1,, a82,, es OD Sps Cis Co, 5 AS 
ae) aly, a2, re 3 asi, C1psis C2pa19 os Eppary lo, 29, eet 
$2, Clpyor €2pgar°* 1 s Epppar’’ *plin 2k, "55 Sky Elon C2anr ** Heme): 


Then the map B? = (¥3,P2) is an orientable map underlying the graph B, and 
stable under the action of (g; hi, ha,-++, An). 

Similarly, replacing each element a1; by $7; in the construction of the ori- 
entable case if h;, = (1, 3), anon-orientable map underlying the graph B,, and stable 
under the action of (g; hi, h2,-+-,hn) can be also constructed. This completes the 
proof. h 

We use the Lemma 3.4.1 for the enumeration of unrooted one face maps on 


surfaces in the next chapter. 


Chapter 4 Application to the Enumeration of Unrooted 
Maps and s-manifolds 


All the results gotten in the Chapter 3 is more useful for the enumeration of 
unrooted maps on surfaces underlying a graph. According to the theory in Chapter 
1, the enumeration of unrooted maps on surfaces underlying a graph can be carried 


out by the following programming: 


STEP 1. Determine all automorphisms of maps underlying a graph; 
STEP 2. Calculate the the fixing set Fx(¢) for each automorphism ¢ of a map; 


STEP 3. Enumerate the unrooted maps on surfaces underlying a graph by 
Corollary 1.3.1. 


The advantage of this approach is its independence of the orientability, which enables 
us to enumerate orientable or non-orientable maps on surafces. We present the 


enumeration results by this programming in this chapter. 


§1. The enumeration of unrooted complete maps on surfaces 


We first consider a permutation and its stabilizer . A permutation with the 
following form (21, ®2,...,U%p)(@Xn,AL2,...,aX1) is called a permutation pair. The 


following result is obvious. 


Lemma 4.1.1 Let g be a permutation on the set Q = {2 1,%2,...,%n} such that 


ga=ag. If 
OCT Bs Pp OTH, OD HA, 15 21)g (UTC c ly Oly OU A Ty OEY); 
then 


g= (Zi; LQy ees Ly) 


and if 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 82 


GOR GI 3kcu, bn) (Oa, OD 24s ..,021)(ga)* Gis 05s ce DH OW a Wig 3 OED), 


then 


Ga — (Ohi Osos ax,)* 


for some integer k,l <k <n. 


Lemma 4.1.2 For each permutation g,g € E satisfying ga = ag on the set 


[RF] 
Q = {x1,22,...,Un}, the number of stable permutation pairs in Q under the action 


of g or ga 1s 
20(k)(n — 1)! 
Ee)| 
where o(k) denotes the Euler function. 
Proof Denote the number of stable pair permutations under the action of g or 
ga by n(g) and C the set of pair permutations. Define the set A = {(9,C)|g € 


EEO €C and C3 =C or C9 =C}. Clearly, for Vgi, 92 € Ei 
n(gi) = N(g2). Whence, we get that 


nb We have 


[Al = [&,2)1n(9). (4.1.1) 


On the other hand, by the Lemma 4.1.1, for any permutation pair C = (x1, £2, ..., £n) 
(QXn,ALn—1,-.-,@X1), since C is stable under the action of g, there must be g = 
(1, £2,...,2n)' Or ga = (AX, ALy-1,...,@21)', where 1 = s?,1<s <k and (s,k) = 
1. Therefore, there are 2¢(k) permutations in Endy acting on it stable. Whence, we 
also have 


|A] = 26(k) ICI. (4.1.2) 


Combining (4.1.1) with (4.1.2), we get that 


_ 20(6)1C] _ 20(8)(0-)! 


n(g) = 4 
Te can 


Teal 


Now we can enumerate the unrooted complete maps on surfaces. 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 83 


Theorem 4.1.1 The number n*(K,) of complete maps of order n > 5 on surfaces 


18 








1 gelnk) (mn — 2\1F (k) 294) (n — 2)!8= 
m(Kr)=s0 0+ do Iam, a 
kln —_k|n,k=0(mod2) e(Z)! k|(n—1), kL Dee 
where, 
nn) if k = 1(mod2); 
a(n, k) = | se) . _ 
, if k=0(mod2), 
and 


@ NG) if k=1(med2); 


tik) = 
Birk) hones if k =0(mod2). 


adn (ha 1 


Proof According to (1.3.3) in the Corollary 1.3.1 and the Theorem 3.2.1 for 
n > 5, we know that 


a) 


n'(Kn) = sya X( VE ml + dE |8(g20)| 
2|Autk,,| giee ti eek 
[kk] [(2s) 2s ] 
+ DF [®(A))) 
he€ n—-1 
[10 e ] 
1 
= x (LE llel+ Xl _ (E,a,1lo20)) 
Hts k|n I|n,l=0(mod2) 


+ YS [E, a l@(A)), 


I(n—1) 


where, 91 € ENR) g2 © Ei and h € an pai, are three chosen elements. 


iT] ; ] 
Without loss of generality, we assume that an element g,g € ER has the 


following cycle decomposition. 


g = (1,2,...,k)(R+ 1k +2, 1 2h). (E =a eae (F ~1)k +2,...,n) 


and 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 84 


P=(I1,xIL: 


where, 


Le ce Oe eee a 


and 


IL, =ed1, eo", 

being a complete map which is stable under the action of g, where s;; € {k+,k—|k = 
Le sat 

Notice that the quadricells adjacent to the vertex ”1” can make 2"~?(n — 
2)!different pair permutations and for each chosen pair permutation, the pair permu- 
tations adjacent to the vertices 2,3,...,k are uniquely determined since P is stable 
under the action of g. 

Similarly, for each given pair permutation adjacent to the vertex k + 1,2k + 
1,...,(¢ —1)k +1, the pair permutations adjacent to k + 2,k +3,...,2k and 2k + 
2,2k+3,...,3k and,...,and (—1)k+2, (4—1)k+3, ...n are also uniquely determined 





because P is stable under the action of g. 

Now for an orientable embedding M, of K,,, all the induced embeddings by 
exchanging two sides of some edges and retaining the others unchanged in M, are 
the same as M, by the definition of maps. Whence, the number of different stable 


embeddings under the action of g gotten by exchanging x and ax in M, for x € 


U,U Cc Xs, where X%j = U {a, Gx}, is 29%, where g(e) is the number of 
orbits of E(K,,) under the action of g and we substract = because we can chosen 
127+,k +14 ,2k+11*,---,n—k+1" first in our enumeration. 


Notice that the length of each orbit under the action of g is k for Vz € E(K,,) 
if k is odd and is x fore = gtd i =1,k+1,---,n-—k+1, or k for all other edges 


if k is even. Therefore, we get that 


g(é) = 


hols ~» 


e(Kn)— 
k ) 





o(Kn) if k = 1(mod2); 
if k =0(mod2). 


Whence, we have that 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 85 








a(n k) — g(e) wee _ mo if k= 1(mod2); 
, k le if k =0(mod2), 

and 
JB(g)| = 20(n — 2), (4.1.3) 


Similarly, if k = 0(mod2), we get also that 


|®(ga)| = 20) (n — 2) 18 (4.1.4) 


for an chosen element g,g € Evy: 


Now for Vh € es , without loss of generality, we assume that h = (1, 2, ..., k) 
(K+ 1,k42,...,2h)...((4= — 1k +1, (4 - 1)k4+2,...,(n—1))(n). Then the above 
statement is also true for the complete graph K,,_; with the vertices 1,2,---,n—1. 
Notice that the quadricells n1*,n?*,---,n”~!* can be chosen first in our enumera- 
tion and they are not belong to the graph K,,_,. According to the Lemma 4.1.2, we 
get that 


|©(h)| = 224) (n, — 217 x ee (4.1.5) 


[Lk F | 


Where 


e(Kn-1) _ n—1 _ ee if k =1(mod2); 


n,k) = h{e) = 5 F aH 
Se wee nt Ue) if k= 0(mod2). 


2k 








Combining (4.1.3) — (4.1.5), we get that 


iF 
n’(Kn) = rhe OS Ee )!P(Go)| + DB Ene ||P (aa) 
3 k|n I|n,l=0(mod2) 
1 ey JE tee PDD 
(nl) 
as = MIZE) (n, — QE zh nl) (pn — 2) 18 
2n! k|n ke(%)! k|n,k=0(mod2) kr (2)! 
n! 26(k)(n — 2)122) (np, — 2) 


=e dy nmol ney a (n—1)! ) 


ices n—-1 
koe (tal) 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 86 


1 20k) (7, — O)IE (k) 29) (mn — 2)! 
= aes S- \— + » a eee: 
k|n — k|n,k=0(mod2) k/* k|(n—1),kA1 
For n = 4, similar calculation shows that n“(K4) = 11 by consider the fixing 
sa and a&€11 1,3) h 


ty .s8p Easytep easy 
For the orientable case, we get the number n?(K,,) of orientable complete maps 


set of permutations in € 


of order n as follows. 


Theorem 4.1.2 The number n°((K,) of complete maps of order n > 5 on orientable 
surfaces 1s 

1 (n — 2)le b(k)(n — 2)! 

M(K)=n+ YEP, yy MeN 


kin Kin,k=o@moaa) BFCE)! ayn nayasé n—1 


and n(K4) = 3. 


Proof According to Tutte’s algebraic representation of map, amap M = (4,3, P) 
is orientable if and only if for Vz € Xy,g, x and aZ@zx are in a same orbit of V3 un- 
der the action of the group V; =< a3,P >. Now applying (1.3.1) in the Corollary 
1.3.1 and the Theorem 3.2.1, Similar to the proof of the Theorem 4.1.1, we get the 


number n°?(K,,) for n > 5 as follows 


as 


nK)= 50+ Yo Seat 


k|n — k|n,k=0(mod2) ks k|(n—-1),kA1 


o(k)(n — 2)!" 

{all 
and for the complete graph Ky, calculation shows that n( Ky) = 3. h 

Notice that n° (K,,) +n (K,,) = n’(K,,). Therefore, we can also get the number 
nN (K,) of unrooted complete maps of order n on non-orientable surfaces by the 
Theorem 4.1.1 and the Theorem 4.1.2 as follows. 


Theorem 4.1.3 The number n\(K,) of unrooted complete maps of order n,n > 5 


on non-orientable surfaces is 


n(K,) = naa ye ) my 
k|ln — k|n,k=0(mod2) ‘ z) 
o(k) (29) — 1)(n — 2)" 
n—-1 


aes 


k|(n—1),k#1 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 87 


and n\ (K4) = 8. Where, a(n, k) and 3(n,k) are same as in Theorem 4.1.1. 


For n = 5, calculation shows that n’(Ks) = 1080 and n?(K;) = 45 based on 
the Theorem 4.1.1 and 4.1.2. For n = 4, there are 3 unrooted orientable maps and 
8 non-orientable maps shown in the Fig.4.1. All the 11 maps of Ay on surfaces are 


non-isomorphic. 





Fig.4.1 


Now consider the action of orientation-preserving automorphisms of complete 


maps, determined in the Theorem 3.2.1 on all orientable embeddings of a complete 
graph of order n. Similar to the proof of the Theorem 4.1.2, we can get the number 
of non-equivalent embeddings of a complete graph of order n, which has been done 


in [43] and the result gotten is same as the result of Mull et al in [54]. 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 88 
§2. The enumeration of a semi-regular graph on surfaces 


The non-equivalent embeddings of a semi-regular graph on surfaces are enu- 
merated in the reference [50]. Here, we enumerate the unrooted maps underlying a 
semi-regular graph on orientable or non-orientable surfaces. 


The following lemma is implied in the proof of the Theorem 4.1 in [50]. 


Lemma 4.2.1 Let l = (V, E) be a semi-regular graph. Then for € € AutI 


9) = TE (OS - ay 


and 
E\_|mv d(x) 
B1(¢)| = gle l-l7e | ih 
| 6) Leh) ) : 


where, Tee are the representations of orbits of € acting on v(T) and E(T) ,re- 


spectively and Ene) the restriction of € to Nr(x). 
r(x) 


According to the Corollary 1.3.1, we get the following enumeration results. 


Theorem 4.2.1 Let T be a semi-regular graph. Then the numbers of unrooted maps 
on orientable and non-orientable surfaces underlying the graph I are 
nT) = Oo xe) TE ($2 
|AutD| 


———— - 1)! 
€€Autl weTY o(f|nr(@)) 


and 


1 
|AutD | 





x MH nae TT (#2 


e¢ Aut ver o(€|nr(e)) 


nN(L) = aii 


where A(E) = 1 if o(€) = 0(mod2) and $, otherwise. 
Proof By the Corollary 1.3.1, we know that 


i 2|Auti.| 


E€Auti Ll 
acai 


n°(L) |®2(9)| 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 89 


and 


L = l Be 


g aur 
According to the Theorem 3.3.4, all the automorphisms of orientable maps 


underlying the graph T are 


g|*~2 and ah|*~9,g,h € Aut with h = 0(mod2). 


and all the automorphisms of non-orientable maps underlying the graph [ are also 


g\*~8 and ah|*=9,g,h € Autl with h = 0(mod2). 


Whence, we get the number of unrooted orientable maps by the Lemma 4.2.1 


as follows. 


n°) = spa © |?) 


geEAutD 


1 d(x) 


€e€Autl 2eTY o(€|n,(2)) 
d(x) 
ts —~_ - 1)! 
a es nce) ) ) 
moe d(x) 
er > ME) IL 


€€AutP weTY o(f|nr(@)) 


27) 


—1)I. 


Similarly, we enumerate the unrooted maps on locally orientable surface under- 
lying the graph T° by (1.3.3) in the Corollary 1.3.1 as follows. 


1 


nT) = aut] 2,2 
= I Oe d(x) 195i 
2|AutD| gcAutl 2eTY o(Elnr(e)) 
i 3 oITEI-ITY | AE) dys 
s€Autl’,o(<s)=0(mod2) xeTY 0(S| r(x) 
1 


- HS xgarebre! yy (Ae) _ ayy 


|AutD| €€Autl weTY o(E|np(a)) 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 90 


Notice that n?([) + nX(L) = n4¥(L), we get the number of unrooted maps on 


non-orientable surfaces underlying the graph I as follows. 


(Lr) = n®(l) =n? (PL) 
i ene ITE|-ITY | _ ae) 
| AutT| ; oem? UAB) LL Seine) " 


This completes the proof. h 
If [ is also a k-regular graph, we can get a simple result for the numbers of 


unrooted maps on orientable or non-orientable surfaces. 


Corollary 4.2.1 Let T be a k-regular semi-regular graph. Then the numbers of 


unrooted maps on orientable or non-orientable surfaces underlying the graph T’ are 





respective 
n?(T) = x A(g)(k — 1)! Fe"! 
") |AutP| oe @) 
and 
1 E Vv Vv 
Np) = glTyI-IT7| — 1) (kb — IITs 
0) =a D Ml )(k = 1), 


gEAutl 
where, A(€) = 1 if o(€) = 0(mod2) and 3, otherwise. 


2? 


Proof In the proof of the Theorem 4.2 in [50], it has been proved that 


Wee VL), — o(€np@)) = 1. 
Whence, we get n?([) and n¥ (I) by the Theorem 4.2.1. h 


Similarly, if 1 = Cay(Z, : 5) for a prime p, we can also get closed formulas for 


the number of unrooted maps underlying the graph [. 


Corollary 4.2.2 Let T = Cay(Z, : S) be connected graph of prime order p with 
(p—1,|S|) =2. Then 


(|S| — 1)” + 2p(/5| — 1)! + (p— 1)((S|- 0)! 


n?(T, M) = 
(P.M) a 


and 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 91 








WMrM) = 2rlaDdsl=pe +2eP EE = pels] yi 
? op 
, SE=)e-Hisl=v! 
4p : 


Proof By the proof of the Corollary 4.1 in [50], we have known that 


1, if o(g)=p 
ITY|=4 8, if og) =2 
p, if o(g)=1 
and 
Bl if o(g)=p 
ITP) =4 2, if o(g) =2 
Le, if o(g) =1 


Notice that Aut’ = D, (see [3]{12]) and there are p elements order 2, one order 
1 and p— 1 order p. Whence, we have 


(|S| — 1)!” + 2p(|5| — 1)!" + (p— 1)((S| - 0)! 


oO a 
ne (LNA) 2 
and 
nM) = CEP USI= py +2283 ~ yptis) — yi 
9 Dp 
, QF ~-1)e-108|-1)! 


Ap 
By the Corollary 4.2.1. h 


§3. The enumeration of a bouquet on surfaces 


For any integer k, k|2n, let F, be the conjugacy class in S;,[.2] with each cycle in 


the decomposition of a permutation in 4, being k-cycle. According to the Corollary 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 92 


1.3.1, we need to determine the numbers |®°(€)| and |®“(€)| for each automorphism 


of a map underlying a graph B,. 


2n/k 
Lemma 4.3.1 Let € = [I (C(i))(aC(i)a7!) € Jy, where, C(t) = (ar, Vig, +++, Vix) 
i=1 
is a k-cycle, be a cycle decomposition. Then 
(i) Ifk #2n, then 


JQ) = eR 1) 


and if k=2n, then |®°(€)| = o(2n). 
(ii) Ifk>3 andk 4 2n, then 


Jo(6)] = (2m) PS yh, 


and 


|&”(€)| = 2"(2n — 1)! 
if € = (21) (£2) +++ (n)(a@1) (aX) ++ + (@Lp) (8X1) (8x2) +++ (Brn) (@BX1)(ABx2) ---(ABZn), 


and 


Je*()| = 1 
if € = (1, @Bx1)(L2, ABT) +++ (Ln, ABLpn) (1, Bx1)(AX2, BXy)+ ++ (AL, BXn), and 
n! 


(n — 2s)!s! 
if E = C3 €1, €2,°-+,En and € € Epjn—2s 98) for some integer s, €; = (1,a8) forl<i<s 


|o"(E)| = 


and é; =1 fors+1<j <n,where, Ejn-2s 95; denotes the conjugate class with the 


type [1"~*5, 2°] in the symmetry group S,, and 


|B” (€)| = o(2n) 
if € = 0321, €9,°°*,En-and @ € €,3) and e; = 1 for 1 <i<n=1, & = (1a), 
where, o(t) is the Euler function. 


Proof (i) Notice that for a given representation of C(i), i = 1,2,---, 7, since 
< P,,a8 > is not transitive on ¥3, there is one and only one stable orientable 


map B, = (¥o,g, Pn) with X = E(B,,) and P, = C(aC~*a~), where, 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 93 


C= (11, 21, va "ysl Be 15 B21 5 L225 a *) Vang, Vik, L2k, ~ *, ©2ng). 


2n 


Counting ways of each possible order for C(i),i = 1,2,---, =, and different repre- 


sentations for C(i), we know that 


J°(@)| = A 1) 


for k A Qn. 
Now if k = 2n, then the permutation itself is a map with the underlying graph 
B,. Whence, it is also an automorphism of the map with the permutation is its 


power. Therefore, we get that 
|&°(€)| = 9(2n) 


(ii) For k > 3 and k ¥ 2n, since the group < P,,afZ > is transitive on Xy,¢ 
or not, we can interchange C(i) by aC(i)~ta~+ for each cycle not containing the 
quadricell 71,;. Notice that we only get the same map if the two sides of some edges 


are interchanged altogether or not. Whence, we get that 


any) 2n_ 4 /2N 2n_1,2n 
jo OL =e he Dh Ok) ero )h 


Now if € = (71, a821) (x2, aBX2) +++ (Xn, WBLn)(AX1, 8X1) (AL2, x2) -+-(ATn, Bn), 


there is one and only one stable map (%4,3, P;) under the action of €, where 


P,, = (fi TQ,° °°, kn, aBaxy, abr, ea aBty)(axr1, Ging mais) xi, AMn,***, ax). 


Which is an orientable map. Whence, |®"”(€)| = |®°(€)| = 1. 
If € = (#1) (2) +++ @n) (x1) (02) + - (tn) (Bar1) (B22) + (Ban) (821) (A,9x2) 


--+(aBx,), we can interchange (aZx;) with (Gx;) and obtain different embeddings 


of B, on surfaces. Whence, we know that 


|b4(6)] = 2"(2n - 1). 


Now if € = (¢;€1,€2,°*+,€n) and ¢ € Ejjn-2s 2s] for some integer s, €; = (1, a) 


for 1 <i<sande,;=1 fors+1<jJj <n, we can not interchange (7;,a(x;) with 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 94 


(ax;,3x;) to get different embeddings of B,, for it just interchanging the two sides 
of one edge. Whence, we get that 
eee a 
1”-25(n — 2s)!28s! (n — 2s)!s! 
For € = (0; €1, €2;°"-,€n), 9 € Ey and e; = 1 for 1 <i < n—1, en = (1, a8), we 
can not get different embeddings of B,, by interchanging the two conjugate cycles, 


whence, we get that 


|” (€)| = |©°(€)| = o(2n). 
This completes the proof. L 
Recall that the cycle index of a group G, denoted by Z(G; 81, 52,°++,5n), is 
defined by ([30]) 


S~ 8} A1( (9) 6 alg Vo. grn(9) 


Z(G 81, 82,°°*, $n) = n 
geG 


ia 
where, A;(g) is the number of i-cycles in the cycle decomposition of g. For the 


symmetric group S;,,, its cycle index is known as follows: 


A1 oA » 
re cee i sik 


ZA Sis 815395°* * 5 Sn) = J>1) !D%2\ol- kw A! 


Ayt2Aq+- +kAp=n 
For example, we have that Z7(S2) = saa By a result of Polya ([56]), we know the 
cycle index of S,,[S2] as follows: 
ae ee 


2 


Z(Sn[S2]; $1, 25° ++, 82n) = 5G D1) 122 \o! Re Ag! 


nl 
an Ai t2rAg+-- +kAp=n 


Now we can count maps on surfaces with an underlying graph B,. 


Theorem 4.3.1 The number n°(B,) of non-isomorphic maps on orientable surfaces 


underlying a graph B, 1s 





n°(B,) = pea oat 0*(Z(SnlS2]))) 
servi k y (=)! Os C 
+ 9(2n) ae 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 95 


Proof According to the formula (1.3.1) in the Corollary 1.3.1, we know that 


PB)=s > YL lS 


€€Sn[S2] xX <a> 
Now since for V1, £2 € S;,[S3], if there exists an element 6 € S,,[S2], such that 


£9 = 0€,0—', then we have that |®°(€,)| = |®°(&)| and |®°(£)| = |®? (€a)|. Notice 
that |®°(€)| has been gotten by the Lemma 4.3.1. Using the Lemma 4.3.1(i) and 
the cycle index 7(S,,[S2]), we get that 





n°(B,) = pE1(22 1) Fe] + 620) |Fonl) 
2x 2"! Ae k 
ee 1 OF (Z(S,|S. 
— a Re = 1)! = ( ( al 2])) lesa 
k|2n,k#2n (=)! Os 


ee 


Now we consider maps on the non-orientable surfaces with an underlying graph 
B,. Similar to the discussion of the Theorem 4.1, we get the following enumeration 


result for the non-isomorphic maps on the non-orientable surfaces. 


Theorem 4.3.2 The number n\(B,) of non-isomorphic maps on the non-orientable 


surfaces with an underlying graph B,, is 


n(B,) = (Cee S- (any — gy EEE) 


| 
Ms k|2n,3<k<2n Osx 


mt guy — yy PC ASalSe))) 
nl (2s Gea aaylal * 2° Wag lemo — Lg) 


Proof Similar to the proof of the Theorem 4.3.1, applying the formula (1.3.3) 
in the Corollary 1.3.1 and the Lemma 4.3.1(7i), we get that 


n’(Bn) = Gn 1 + 620) D0 
1 n! 0"(Z(Sn[S2])) 


te 


0 (n — 2s)!s! 


- ye (ony OE (ZSnlS2))) 


kl2n,3<k<2n Os, 


pF A= I None ~ 151) 





Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 96 


Notice that n?(B,) +n%(B,) = n*(B,). Applying the result in the Theorem 
4.3.1, we know that 


Qn, OF (Z(Sn[So])) 


ne k|2n,3<k<2n k Os; 
1 n! 0" (Z(S;,[S2])) n 
— ———_—_ + 4"(n — 1)!|(—————+ |...-0 — |=])). 
2”n! oe (n — 2s)!s! rai Osh |sa=0 5) 
This completes the proof. h 
Calculation shows that 

si + S82 
Z(S1[S9]) = a 


and 


si + 25785 + 382 + 2s 
Z(S5|S5\)= ee 


For n = 2, calculation shows that there are 1 map on the plane, 2 maps on the 
projective plane, 1 map on the torus and 2 maps on the Klein bottle. All of those 
maps are non-isomorphic and same as the results gotten by the Theorem 4.3.1 and 
4.3.2, which are shown in the Fig. 2. 





Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 97 


84. A classification of the closed s-manifolds 


According to the Theorem 1.2.8, We can classify the closed s-manifolds by 


triangular maps with valency in {5,6,7} as follows: 


Classical Type: 


(1) Ay = {5 — regular triangular maps} (elliptic); 
(2) Ay = {6 — regular triangular maps}(euclid); 
(3) As = {7 — regular triangular maps}(hyperbolic). 


Smarandache Type: 


(4) Ay = {triangular maps with vertex valency 5 and 6} (euclid-elliptic); 

(5) As = {triangular maps with vertex valency 5 and 7} (elliptic-hyperbolic); 
(6) Ag = {triangular maps with vertex valency 6 and 7} (euclid-hyperbolic); 
(7) A; = {triangular maps with vertex valency 5,6 and 7} (mized). 


We prove each type is not empty in this section. 


Theorem 4.4.1 For classical types A, ~ A3, we have that 
(1) Ai = {O20, Pro}; 
(2) Ao = {Ti, Kj,1 < t,7 < +00}; 
(3) As = {Hi,1 <i < +oco}, 
where, Oo, Pio are shown in the Fig.4.3, Tz, K3 are shown in the Fig. 4.4 and H; 


is the Hurwitz maps, i1.e., triangular maps of valency 7. 





20 


Fig. 4.3 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 98 





Fig. 4.4 


Proof If M is a k-regular triangulation, we get that 2¢(M) = 36(M) = kv(M). 


Whence, we have 








e(M) = 50M) and v(M) = aN) 
By the Euler-Poincare formula, we know that 
x(M) = o(M) — e(M) + 6(M) = (2 - 5)6(M) 
If M is elliptic, then k = 5. Whence, x(M) = on) > 0. Therefore, if M 


is orientable, then x(M) = 2, Whence, ¢(M) = 20,v(M) = 12 and e(M) = 30, 
which is the map Ogg. If if M is non-orientable, then x(/) = 1, Whence, ¢(M) = 
10,v(M) = 6 and ¢(M) = 15, which is the map Pip. 

If M is euclid, then k = 6. Whence, x(M) = 0, ie., M is a 6-regular tri- 
angulation T; or K; for some integer 7 or j on the torus or Klein bottle, which is 
infinite. 

If M is hyperbolic, then k = 7. Whence, x(M@) < 0. M is a 7-regular 
triangulation, i.e., the Hurwitz map. According to the results in [65], there are 
infinite Hurwitz maps on surfaces. This completes the proof. h 

For the Smarandache Types, the situation is complex. But we can also obtain 
the enumeration results for each of the types A, ~ Az. First, we prove a condition 


for the numbers of vertex valency 5 with 7. 


Lemma 4.4.1 Let Let C(T,n) be an s-manifold. Then 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 99 


Ur > Us +2 


if x(C(T,n)) < —1 and 


Uz <5 — 2 
if x(C(T,n)) > 1. where v; denotes the number of vertices of valency i in C(T,n). 


Proof Notice that we have know 


e(C(T,n)) = —{ 
3 
where & is the average valency of vertices in C(T,n). Since 


_ 5U5 + 6u6 + Tv7 
7 Us + Ug + U7 
and <(C(T,n)) > 3. Therefore, we get that 
(i) If x(C(T,n)) < -1, then 





iP <2 2 2 
1 2us + 2ue+2er . 4 
3 5u5 + bug + Tv7 


i.e., V7 > v5 + 1. Now if v7 = v5 + 1, then 











5Us + 6u¢ + Tv7 = 12v5 + 6u¢ +7= 1(mod2). 


Contradicts to the fact that Devi) pr(v) = 2e(T) = O(mod2) for a graph TI. 
Whence we get that 


U7 > Us + 2. 


(iz) If x(C(T,n)) > 1, then 


1 2 2 2 
1 2us + 2ue+2er _ 9 
3. 5us5 + 6ug + Tv7 


i.e., v7 < us — 1. Now if v7 = vs — 1, then 














5s + 6ug + Tv7 = 12u5 + 6ue — 7 = 1(mod2). 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 100 


Also contradicts to the fact that Dyevr) pr(v) = 2e(T) = 0(mod2) for a graph YP. 
Whence, we have that 


U7 < Us — 2. h 
Corollary 4.4.1 There is no an s-manifold C(T,n) such that 


|uz _ Us| < 1, 
where vu; denotes the number of vertices of valency 7 in C(T,n). 
Define an operator =: M — M* on a triangulation M of a surface as follows: 
Choose each midpoint on each edge in M and connect the midpoint in each 
triangle as shown in the Fig.4.5. Then the resultant M* is a triangulation of the 


same surface and the valency of each new vertex is 6. 


Yi Ga 


Wf C a4 


Fig. 4.5 
Then we get the following result. 


Theorem 4.4.2 For the Smarandache Types A, ~ Az, we have 
(i) |As| 2 2; 
(it) Each of |Aq],|Ag| and |Az7| is infinite. 


Proof For M © Ag, let k be the average valency of vertices in M, since 


5Us + 6 
kao <6 and ¢(M) = 


U5 +1 U6 


=x(M) 








’ 


wile 
[by 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 101 


we have that y(M) > 1. Calculation shows that v; = 6 if y(M) = 1 and vs = 12 if 
y(M) = 2. We can construct a triangulation with vertex valency 5,6 on the plane 


and the projective plane in the Fig. 4.6. 





(a) (b) 


Fig. 4.6 
Now let M be a map in the Fig. 4.6. Then M® is also a triangulation of the 
same surface with vertex valency 5,6 and M° 4 M. Whence, |A4| is infinite. 
For M € As, by the Lemma 4.4.1, we know that v7 < vs — 2 if x(W) > 1 and 
U7 > vs + 2 if y(M) < —1. We construct a triangulation on the plane and on the 
projective plane in the Fig.4.6. 





(a) (b) 
Fig. 4.7 


Chapter 4 Application to the Enumeration of Unrooted Maps and s-Manifolds 102 


For M € Ag, we know that k = Sut Tve > 6. Whence, x(M) < —1. Since 


6U 


3¢(M) = 6ug + Tv7 = 2e(M), we get that 





66 + Tv7 ai 6u¢ + Tv7 = 
2 Be 7 


Therefore, we have v7 = —x(M). Since there are infinite Hurwitz maps M on 


Ug + U7 — x(M). 


surfaces. Then the resultant triangular map M* is a triangulation with vertex 
valency 6,7 and M* # M. Whence, |Ag| is infinite. 
For M € Az, we construct a triangulation with vertex valency 5,6, 7 in the Fig. 


4.8 as follows. 





Fig. 4.8 
Let M be one of the maps in the Fig.4.8. Then the action of 0 on M results 


infinite triangulations of valency 5,6 or 7. This completes the proof. h 


Conjecture 4.4.1. The number |As5| is infinite. 


Chapter 5 Open Problems for Combinatorial Maps 


As a well kind of decomposition of a surface, maps are more concerned by math- 
ematician in the last century, especially in the enumeration of maps ({33] —[35]) and 
graphs embedding on a surface ({22], [35], [53], [70]). This has its own right,also its 
contribution to other branch of mathematics and sciences. Among those map ap- 
plication to other branch mathematics, one typical example is its contribution to 
the topology for the classification of compact surfaces by one face, or its dual, one 
vertex maps, i.e., a bouquet B, on surfaces. Another is its contribution to the group 
theory for finding the Higman-Sims group (a sporadic simple group ([{6])) and an 
one sentence proof of the Nielsen-Schreier theorem, i.e., every subgroup of a free 
group is also free ({63] — [64]). All those applications are to the algebra, a branch of 
mathematics without measures. From this view, the topics discussed in the graph 
theory can be seen just the algebraic questions. But our world is full of measures. 
For applying combinatorics to other branch of mathematics, a good idea is pullback 
measures on combinatorial objects again, ignored by the classical combinatorics and 
reconstructed or make combinatorial generalization for the classical mathematics, 
such as, the algebra, differential geometry, Riemann geometry, Smarandache ge- 
ometries, --- and the mechanics, theoretical physics, ---. For doing this, the most 
possible way is, perhaps by the combinatorial maps. Here is a collection of open 


problems concerned maps with the Riemann geometry and Smarandache geometries. 


5.1 The uniformization theorem for simple connected Riemann sur- 


faces 


The uniformization theorem for simple connected Riemann surfaces is one of 


those beautiful results in the Riemann surface theory, which is stated as follows(([18]). 


If S is a simple connected Riemann surface, then S is conformally equivalent 
to one and only one of the following three: 

(a) CUoo; 

(b) C; 


Chapter 5 Open Problems for Combinatorial Maps 104 


(ey Aree fee ell <1). 


We have proved in the Chapter 2 that any automorphism of a map is conformal. 
Therefore, we can also introduced the conformal mapping between maps. Then, how 
can we define the conformal equivalence for maps enabling us to get the uniformiza- 
tion theorem of maps? What is the correspondence class maps with the three type 


(a) — (c) Riemann surfaces? 


5.2 The Riemann-Roch theorem 


Let S be a Riemann surface. A divisor on S is a formal symbol 


u= ll pei 


i=l 
with P; € S, a(P;) € Z. Denote by Div(S) the free commutative group on the 
points in S and define 


degu = S- a(P,). 


i=l 
Denote by H(S) the field of meromorphic function on S. Then for Vf € H(S) \ 
{0}, f determines a divisor (f) € Div(S) by 


(f) = II IPs, 


PES 
where, if we write f(z) = 2"g(z) with g holomorphic and non-zero at z = P, then 


the ordpf =n. For U, = JT P™),U. = [] P@?),€ Div(S), call U, > Up if 
PEs Pes 
ai(P) > a2(P). Now we define a vector space 


LU) ={f © H(S)(f) 2U,U € Div(S)} 


Q(U) = {w|w is an abelian dif ferential with (w) > U}. 


The Riemann-Roch theorem says that([71]) 


dim(L(U~")) = deg — g(S) +1+ dimQ(S). 


Chapter 5 Open Problems for Combinatorial Maps 105 


Comparing with the divisors and their vector space, there ia also cycle space 
and cocycle space in graphical space theory ([35]). What is their relation? Whether 


can we rebuilt the Riemann-Roch theorem by map theory? 


5.3 Combinatorial construction of an algebraic curve of genus 


A complex plane algebraic curve C; is a homogeneous equation f (x,y,z) = 0 
in P»C = (C? \ (0,0,0))/ ~, where f(z,y,z) is a polynomial in x,y and z with 
coefficients in C. The degree of f(x,y, z) is said the degree of the curve Cj. For 
a Riemann surface S, a well-known result is ({71])there is a holomorphic mapping 
yp: 5S — P2C such that y(S) is a complex plane algebraic curve and 

(d(y(S)) — 1)(d(y(S)) — 2) 


g(S') = a 


By map theory, we know a combinatorial map also is on a surface with genus. 
Then whether we can get an algebraic curve by all edges in a map or by make 
operations on the vertices or edges of the map to get plane algebraic curve with 


given k-multiple points? and how do we find the equation f(x,y, z) = 0? 


5.4 Classification of s-manifolds by maps 


We have classified the closed s-manifolds by maps in the Section 4 of Chapter 4. 
For the general s-manifolds, their correspondence combinatorial model is the maps 
on surfaces with boundary, founded by Bryant and Singerman in 1985 ([8]). The 
later is also related to the modular groups of spaces and need to investigate further 


itself. The questions are 


(i) how can we combinatorially classify the general s-manifolds by maps with 
boundary? 

(it) how can we find the automorphism group of an s-manifold? 

(iii) how can we know the numbers of non-isomorphic s-manifolds, with or 
without root? 

(iv) find rulers for drawing an s-manifold on a surface, such as, the torus, the 


projective plane or Klein bottle, not the plane. 


Chapter 5 Open Problems for Combinatorial Maps 106 


The Smarandache manifolds only using the triangulations of surfaces with ver- 
tex valency in {5,6,7}. Then what are the geometrical mean of the other maps, such 
as, the 4-regular maps on surfaces. It is already known that the later is related to 
the Gauss cross problem of curves([35]). May be we can get a geometry even more 


general than that of the Smarandache geometries. 


5.5 Gauss mapping among surfaces 


In the classical differential geometry, a Gauss mapping among surfaces is defined 
as follows(({42]): 


Let S C R? be a surface with an orientation N. The mapping N : S > R° 


takes its value in the unit sphere 


S? = {(2,y,2) € Biz? +y? +2 =1} 
along the orientation N. The map N: S — S?, thus defined, is called the Gauss 
mapping. 


we know that for a point P € S such that the Gaussian curvature K(P) 4 0 

and V a connected neighborhood of P with K does not change sign, 
ACP lim ne: 

where A is the area of a region B C V and N(A) is the area of the image of B by 
the Gauss mapping N : S — S?. The questions are 

(i) what is its combinatorial meaning of the Gauss mapping? How to realizes 
it by maps? 

(it) how we can define various curvatures for maps and rebuilt the results in 


the classical differential geometry? 


5.6 The Gauss-Bonnet theorem 


Let S be a compact orientable surface. Then 


Chapter 5 Open Problems for Combinatorial Maps 107 


| [ Kao = 2nx(8), 


where K is Gaussian curvature on S. 

This is the famous Gauss-Bonnet theorem for compact surface (({14], [71] — [72]). 
This theorem should has a combinatorial form. The questions are 

(i) how can we define the area of a map? (Notice that we give a definition of 
non-Euclid area of maps in Chapter 2.) 


(ii) can we rebuilt the Gauss-Bonnet theorem by maps? 


5.7 Riemann manifolds 


A Riemann surface is just a Riemann 2-manifold. A Riemann n-manifold (M, g) 
is a n-manifold M with a Riemann metric g. Many important results in Riemann 
surfaces are generalized to Riemann manifolds with higher dimension ([14], [71] — 
[72]). For example, let M be a complete, simple-connected Riemann n-manifold 
with constant sectional curvature c, then we know that M is isometric to one of the 
model spaces R”, Srn or Hrn. There is also a combinatorial map theory for higher 
dimension manifolds (see [67] — [68]). Whether can we systematically rebuilt the 
Riemann manifold theory by combinatorial maps? or can we make a combinatorial 
generalization of results in the Riemann geometry, for example, the Chern-Gauss- 
Bonnet theorem ((14], [37], |71])? If we can, a new system for the Einstein’s relative 


theory will be found. 











12 


13 


14 








References 


R.D.M.Accola, On the number of automorphisms of a closed Riemann surface, 
Tran.Amer.Math.Soc.,vol.131,398-408(1968). 

N.L.Alling, Foundation of the theory of Klein surfaces, Lect.notes in Math.,219, 
Springer-Verlag, Berlin,etc.(1971). 

B.Alspach, Point-symmetric graphs and digraphs of prime order and transitive 
permutation groups of prime degree, J.Combin.Theory,Ser.B, 15(1973),12-17. 
C.Ashbacher, Smarandache geometries, Smarandache Notions Journal, Vol.8, 
No. 1-2-3(1997),212-215. 

L.Babai,Automorphism groups, isomorphism, reconstruction, in R. Graham, 
M.Grotschel and L.Lovasz ed: Handbook of Combinatorics,Elsevier Science B.V, 
(1995), 1447-1540. 

N.L.Biggs and A.T.White, Permutation Groups and Combinatoric Structure, 
Cambridge University Press (1979). 

L.Brankovic, M.Miller et al, A note on constructing large Cayley graphs of given 





degree and diameter by voltage assignments, The Electronic J. Combinatorics, 
5(1998),#R9. 

R.P.Bryant and D.Singerman, Foundations of the theory of maps on surfaces 
with boundary, Quart. J. Math. Oxford(2),36(1985), 17-41. 

E.Bujalance, Cyclic group automorphisms of compact non-orientable Klein sur- 
faces without boundary, Pacific J. Mathematics, vol.109, No.2,279-289(1983). 
E. Bujalance,J.J.Etayo and J.M.Gamboa, Hyperelliptic Klein surfaces, Qurt. 
J. Math. Oxford(2),36(1985), 141-157. 

E.Bujalance,J.J.Etayo,J.M.Gamboa and G.Gromadzki, Automorphism groups of 
compact bordered Klein surfaces, Lect.notes in Math.,1439, Springer-Verlag, 
Berlin,etc. (1990). 

C.Y.Chao, On the classification of symmetrical graphs with a prime number of 
vertices, Trans.Amer.Math.Soc. 158(1971), 247-256. 

J.Chern, J.L.Gross and R.G.Rieper, Overlap matrices and total imbedding dis- 
tributions, Discrete Math.128(1994) ,73-94. 

S.S.Chern and W.H.Chern, Lectures in Differential Geometry, Peking Univer- 
sity Press, 2001. 


References 109 


15 


16 


ils 


18 
19 








20 


22 
23 


24 


25 


26 








21 


28 


29 


30 








dl 


B.P.Chetia and K.Patra, On metabelian groups of automorphisms of compact 
Riemann surfaces, J.London Math. Soc, Vol.33,No.2, 467-472(1986). 
S.Chimienti and M.Bencze, Smarandache paradoxist geometry, Bulletin of Pure 
and Applied Sciences, Delhi, India, Vol.17E, No.1(1998), 123-1124. 
J.Edmonds, A combinatorial representation for polyhedral surfaces, Notices 
Amer. Math. Soc 7 (1960) 

H. M.Farkas and I. Kra, Riemann Surfaces, Springer-Verlag New York inc(1980). 
M.L.Furst, J.L.Gross and R.Statman, Genus distributions for two class of graphs, 
J.Combin. Theory, Ser B, 46(1989) ,22-36. 

A.Gardiner,R.Nedela,J.Sirai and M.Skovera, characterization of graphs which 
underlie regular maps on closed surfaces, J.London Math. Soc.(2)59(1999),100- 
108. 

G.Gromadzki, Abelian Groups of automorphisms of compact non-orientable 
Klein surfaces without boundary, Commentationes Mathematicae, 28(1989) ,197- 
217. 

J.L.Gross and T.W.Tucker, Topological graph theory, John Wiley & Sons,1987. 
J.L.Gross and M.L.Furst, Hierarchy for imbedding-distribution invariants of a 
graph, J.Graph Theory,11(1987), 205-220. 

J.L.Gross and M.L.Furst, Genus distribution for bouquets of circles, J. Combin. 
Theory, Ser B, 47(1989), 292-306. 

F.Harary and W.T.Tutte, On the order of the group of a planar map, J.Combin. 
Theory, 1(1966), 194-195. 

W.J.Harwey,Cyclic groups of automorphisms of compact Riemann surfaces, 
Quart J.Math. Oxford, vol.17, No.2, 86-97(1966). 

H.Iseri, Smarandache Manifolds, American Research Press, Rehoboth, NM, 
2002. 

H.Iseri, Partially Paradozxist Smarandache Geometries, http://www.gallup.unm. 
edu/Smarandache/Howard-Iseri-paper.htm. 

G.A.Jones and D.Singerman, Theory of maps on orientable surfaces, Proc. London 
Math. Soc.(3),37(1978),273-307. 

V.Krishnamurthy, Combinatorics: Theory and Application, Ellis Horwood Lim- 
ited, 1986. 

J.H.Kwak and S.H.Shim, Total embedding distribution for bouquets of circles, 


References 110 


[32] 


33 


34 


35 


36 


37 
38 


39 


40 


41 


42 


43 


44 








Discrete Math.248(2002) ,93-108. 
L.Kuciuk and M.Antholy, An Introduction to Smarandache Geometries, Math- 
ematics Magazine, Aurora, Canada, Vol.12(2003), and online: 
http://www.mathematicsmagazine.com/1-2004/Sm_Geom_1_2004. htm; 
also at New Zealand Mathematics Colloquium, Massey University, Palmerston 
North, New Zealand, December 3-6,2001 
http: //atlas-conferences.com/c/a/h/f/09.htm; 
also at the International Congress of Mathematicians (ICM2002), Beijing, China, 
20-28, August, 2002, 
http://www.icm2002.org.cn/B/Schedule.Section04. htm. 
Y.P.Liu, Enumerative Theory of Maps, Kluwer Academic Publishers , Dor- 
drecht / Boston/ London,1999. 
Y.P.Liu, Advances in Combinatorial Maps, Northern Jiaotong University Pub- 
lisher, Beijing (2003). 
Y.P.Liu, Embeddability in Graphs, Kluwer Academic Publisher, Dordrecht / 
Boston / London (1995). 
Y.P. Liu, The maximum non-orientable genus of a graph (in Chinese), Scientia 
Sinica (Special Issue on Math),1(1979),191-201. 
J.M.Lee, Riemann Manifolds, Springer-Verlag New York,Inc(1997). 
Lv Y.N. and Zhang X.L.Riemann Surfaces, Sciences Publisher Press, Beijing, 
1991. 
C.Maclachlan, Abelian groups of automorphisms of compact Riemann surfaces, 
Proc. London Math. Soc., vol.15,No.3,699-712(1965). 
A.Malnic, Group action,coverings and lifts of automorphisms, Discrete Math, 
182(1998) 203-218. 
A.Malinic,R.Nedela and M.Skoviera, Lifting graph automorphisms by voltage 
assignment, Europ. J.Combinatorics, 21(2000),927-947. 
Mantredo P.de Carmao, Differential Geometry of Curves and Surfaces, Pearson 
Education asia Ltd (2004). 


L.F.Mao, A census of maps on surface with given underlying graph, A doctor 





thesis in Northern Jiaotong University, Beijing, 2002. 
L.F.Mao and Y.P.Liu, New automorphism groups identity of trees, Chinese 
Advance in Math. ,113-117,5(2002). 


References 111 


45 


46 


AT 








48 


[49] 


[50] 


51 


52 


53 


54 








59 


56 


57 


58 








59 


L.F.Mao and Y.P.Liu, On the roots on orientable embeddings of graph, Acta 
Math. Scientia, 23A(3),287-293(2003). 

L.F.Mao and Y.P.Liu, Group action approach for enumerating maps on sur- 
faces, J.Applied Math. & Computing, vol.13, No.1-2,201-215. 

L.F.Mao and Y.P.Liu, A new approach for enumerating maps on orientable 
surfaces, Australasian J. Combinatorics, vol.30(2004), 247-259. 

L.F.Mao and Y.P.Liu, The semi-arc automorphism group of a graph with ap- 





plication to map enumeration, Graphs and Combinatorics(accepted and to ap- 
pear). 

L.F.Mao and Y.P.Liu, Automorphisms of maps with underlying Cayley graph 
and their application to enumeration, Submitted to Discrete Math. 

L.F.Mao, Y.P.Liu and F.Tian, Automorphisms of maps with a given underlying 
graph and their application to enumeration, Acta Mathematica Sinica, Vol.21, 
2(2005),225-236. 

L.F.Mao and F.Tian, On oriented 2-factorable graphs, J.Appl.Math. & Com- 
puting, Vol.17(2005), 25-38. 

W.S.Massey, Algebraic topology: an introduction, Springer-Verlag,New York, 
etc.(1977). 

B.Mohar and C.Thomassen, Graphs on Surfaces, The Johns Hopkins University 
Press, London, 2001. 

B.P.Mull,R.G.Rieper and A.T.White, Enumeration 2-cell imbeddings of con- 
nected graphs, Proc. Amer. Math.Soc., 103(1988), 321 330. 

B.P.Mull, Enumerating the orientable 2-cell imbeddings of complete bipartite 
graphs, J.Graph Theory, vol 30, 2(1999),77-90. 

R.Nedela and M Skoviera, Regular embeddings of canonical double coverings 
of graphs, J.combinatorial Theory,Ser.B 67, 249-277(1996). 

R.Nedela and M.Skoviera, Regular maps from voltage assignments and expo- 
nent groups, Europ. J.Combinatorics, 18(1997),807-823. 

PlanetMath, Smarandache Geometries, http://planetmath.org/encyclopedia/ 
SmarandacheGeometries.htm1. 

K.Polthier and M.Schmies, Straightest geodesics on polyhedral surfaces, in 
Mathematical Visualization (ed. by H.C.Hege and K.Polthier), Springer-Verlag, 
Berlin, 1998. 


References 112 


60 


61 


62 
63 





64 


65 


66 


67 
68 


69 
70 


71 


72 








73 











D.Singerman, Automorphisms of compact non—orientable Riemann surface, Glas- 
gow J. math., 12(1971), 50-59. 

F.Smarandache ,Paradoxist mathematics, Collected Papers,Vol.,II, 5-28, Uni- 
versity of Kishinev Press, 1997. 

S.Stahl, Generalized embedding schemes, J.Graph Theory 2,41-52,1978. 
T.R.Stallings, Graphical theory of automorphisms of free groups, in Combinato- 
rial group theory and topology(ed. by S.M.Gersten and J.R.Stallings), Princeton 
University Press,1987. 

J.Stillwell, Classical topology and combinatorial group theory, Springer-Verlag 
New York Inc., (1980). 

D.B.Surowski, Lifting map automorphisms and MacBeath’s theorem, J. Com- 
bin. Theory, Ser B,50(1990),135-149. 

W.T.Tutte, What is a maps? in New Directions in the Theory of Graphs (ed.by 
F.Harary), Academic Press (1973), 309 325. 

A.Vince, Combinatorial maps,J. Combin. Theory, Ser B 34 (1983), 1-21. 
A.Vince, Regular combinatorial maps, J. Combin. Theory, Ser B 35 (1983),256- 
206 

J.K.Weeks, The shape of Space, New York, Marcel Dekkler, Inc, 1985. 
A.T.White, Graphs of Group on Surfaces- interactions and models, Elsevier 
Science B.V. (2001). 

H.X.Wu, Y.N.Lv and Z.H.Chern, Introduction to Compact Riemann Surfaces, 
Science Publisher Press, Beijing, 1999. 

H.X.Wu, C.L.Shen and Y.L.Yu,Elementary Riemann Geometry, Peking Uni- 
versity Press, 1989. 

M.Y.Xu, Introduction to the Finite Groups (1), Science Publisher Press, Beijing, 
1999. 


Index 


algebraic curve 105 
atlas 1 

analytic function 1 
angle 42 

angle transformation 42 
antianalytic function 1 


asymmetric graph 19 


automorphism of a graph 13 


automorphism of a Klein surface 4 


automorphism of amap 10 


automorphism of an s-manifold 4 


boundary 2 


Burnside Lemma _ 17 


Cauhy-Riemann equation 
classical type of s-manifolds 
complete map 63 
connected graph 5 
covering mapping 31 


cycle index of a group 94 


degree of acurve 105 
dianalytic function 1 
divisor 104 

dual map 8 


elliptic vertex 3 
embedding of a graph 6 
embedding sequence 24 
equivalent embedding 10 


Euclid vertex 3 


ib 


re 


Euler-Poincaré formula 7 
fixed-free action 36 


Gauss-Bonnet theorem 106 
Gauss mapping 105 
graph 4 

graphical property 44 


Hurwitz theorem 44 


hyperbolic vertex 3 


incidence of semi-arc 14 
induced action 57 
isomorphic s-manifolds 4 


isomorphism between maps 10 


Klein group 8 


Klein surface 1 
lifting map 34 


map 8 
model of Klein surfaces 11 
model of closed s-manifold 12 


morphism 3 


NEC group 4 
non-Euclid area 42 
non-orientable genus polynomial 21 


non-orientable map 9 


order of agraph 5 

orientable genus polynomial 21 
orientable map 9 
orientation-preserving automorphism 57 


orientation-reversing automorphism 57 


path 5 


Index 


permutation pair 81 underlying graph 9 
pure rotation 6 uniformization theorem 


pure rotation system 6 
voltage map 33 


quadricell 8 i‘ 
wa 
quadricell set 31 


quotient map 37 y-linear 24 


Riemann-Hurwitz equation 51 
Riemann-Hurwitz formula 43 
Riemann n-manifold 106 


Riemann surface 1 


root vertex 14 

rooted map 9 

rooted map sequence 24 

rooted non-orientable map polynomial 20 
rooted orientable map polynomial 20 
rooted total map polynomial 20 


rotation system 7 


semi-arc 14 

semi-arc automorphism of a graph 14 
semi-regular graph 73 

semi-regular map 73 

simple graph 5 

size of a graph 5 

s-manifold 3 

Smarandachely denied 3 
Smarandache geometry 3 


Smarandache type of s-manifolds 97 


total genus polynomial 21 
trail 5 

type 1 edge 7 

type 0 edge 7 


114 


104 


About the Author 


Linfan Mao is a post-doctor in the Academy of Mathematics and Systems of Chinese 
Academy of Sciences in Beijing, P.R.China, where he lives with his wife Tieying 
Wang and daughter Beigi Mao. His main interesting focus on the combinatorial 
map theory, differential geometry and Smarandache geometries and published more 
than 20 papers on the combinatorial maps, graphs and operation research in journals. 
He was born in December 31,1962 and got his BA in applied mathematics in Peking 
University in 1995 learnt by himself. In 2002, he got a PhD from the Northern 
Jiaotong University (Now the Beijing Jiaotong University) with a doctoral thesis 
A census of maps on surface with given underlying graph under the supervision of 
Professor Yanpei Liu. He was a worker from 1982 to 1987 and then an engineer in 
China Construction Second Engineering Bureau First Company until March,1999. 
After that, he become a doctor graduate student and also a senior engineer and 
a consultor in Guoxin Tendering Co., Ltd. until June,2003. Then he works in 
the Academy of Mathematics and Systems of Chinese Academy of Sciences as a 


post-doctor. 


Abstract 


A combinatorial map is a connected topological graph cellularly embedded 
in a surface. This monograph concentrates on the automorphism group 
of a map, which is related to the automorphism groups of a Klein surface 
and a Smarandache manifold, also applied to the enumeration of unrooted 
maps on orientable and non-orientable surfaces. A number of results for the 
automorphism groups of maps, Klein surfaces and Smarandache manifolds 
and the enumeration of unrooted maps underlying a graph on orientable 
and non-orientable surfaces are discovered. An elementary classification for 
the closed s-manifolds is found. Open problems related the combinatorial 
maps with the differential geometry, Riemann geometry and Smarandache 
geometries are also presented in this monograph for the further applications 


of the combinatorial maps to the classical mathematics. 


ISSN 1+931233-92-6 
9 °781931°233927