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


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: //

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: smarandache/eBooks-otherformats.htm ISBN:1-931233-92-6

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


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


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 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


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)!


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, 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


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


(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


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}. 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