Kapa & Omega, Glendale, AZ USA


Yanpei LIU

Institute of Mathematics Beijing Jiaotong University Beijing 100044, P.R.China Email: ypliu@bjtu.edu.cn

Introductory Map Theory

Kapa & Omega, Glendale, AZ USA


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

Peer Reviewers:

L.F.Mao, Chinese Academy of Mathematics and System Science, P.R.China. J.L.Cai, Beijing Normal University, P.R.China.

H.Ren, East China Normal University, P.R.China.

R.X.Hao, Beijing Jiaotong University, P.R.China.

Copyright 2010 by Kapa & Omega, Glendale, AZ and Yanpei Liu

Many books can be downloaded from the following Digital Library of Science:

http: //www.gallup.unm.edu/~smarandache/eBooks-otherformats.htm

ISBN: 978-1-59973-134-6

Printed in America


Maps as a mathematical topic arose probably from the four color problem|Bir1, Orel] and the more general map coloring problem|HiC1, Rinl, Liu11] in the mid of nineteenth century although maps as poly- hedra which go back to the Platonic age. I could not list references in detail on them because it is well known for a large range of readers and beyond the scope of this book. Here, I only intend to present a comprehensive theory of maps as a rigorous mathematical concept which has been developed mostly in the last half a century.

However, as described in the book[Liu15| maps can be seen as graphs in development from partition to permutation and as a basis extended to Smarandache geometry shown in [Mao3-4]. This is why maps are much concerned with abstraction in the present stage.

In the beginning, maps as polyhedra were as a topological, or ge- ometric object even with geographical consideration|Kem1]. The first formal definition of a map was done by Heffter from [Hef1] in the 19th century. However, it was not paid an attention by mathematicians until 1960 when Edmonds published a note in the AMS Notices with the dual form of Heffter’s in |Edm1,Liu3].

Although this concept was widely used in literature as [Liul—2, Liu4—6, Rin1-3, Stal-2, et all, its disadvantage for the nonorientable case involved does not bring with some convenience for clarifying some related mathematical thinking.

Since Tutte described the nonorientability in a new way [Tut1- 3], a number of authors begin to develop it in combinatorization of continuous objects as in [Lit1, Liu7-10, Vin1-2, et al].

The above representations are all with complication in construct- ing an embedding, or all distinct embeddings of a graph on a surface.

lv Preface

However, the joint tree model of an embedding completed in recent years and initiated from the early articles at the end of seventies in the last century by the present author as shown in [Liul—2] enables us to make the complication much simpler.

Because of the generality that an asymmetric object can always be seen with some local symmetry in certain extent, the concepts of graphs and maps are just put in such a rule. In fact, the former is corresponding to that a group of two elements sticks on an edge and the later is that a group of four elements sticks on an edge such that a graph without symmetry at all is in company with local symmetry. This treatment will bring more advantages for observing the structure of a graph. Of course, the later is with restriction of the former because of the later as a permutation and the former as a partition.

The joint tree representation of an embedding of a graph on two dimensional manifolds, particularly surfaces(compact 2-manifolds without boundary in our case), is described in Chapter I for simplifying a number of results old and new.

This book contains the following chapters in company with re- lated subjects.

In Chapter I, the embedding of a graph on surfaces are much concerned because they are motivated to building up the theory of abstract maps related with Smarandache geometry.

The second chapter is for the formal definition of abstract maps. One can see that this matter is a natural generalization of graph em- bedding on surfaces.

The third chapter is on the duality not only for maps themselves but also for operations on maps from one surface to another. One can see how the duality is naturally deduced from the abstract maps described in the second chapter.

The fourth chapter is on the orientability. One can see how the orientability is formally designed as a combinatorial invariant. The fifth chapter concentrates on the classification of orientable maps. The sixth chapter is for the classification of nonorientable maps.

From the two chapters: Chapter V and Chapter VI, one can see

Preface v

how the procedure is simplified for these classifications.

The seventh chapter is on the isomorphisms of maps and pro- vides an efficient algorithm for the justification and recognition of the isomorphism of two maps, which has been shown to be useful for de- termining the automorphism group of a map in the eighth chapter. Moreover, it enables us to access an automorphism of a graph.

The ninth and the tenth chapters observe the number of distinct asymmetric maps with the size as a parameter. In the former, only one vertex maps are counted by favorite formulas and in the latter, general maps are counted from differential equations. More progresses about this kind of counting are referred to read the recent book|Liu7] and many further articles|«Bax1, BeG1, CaL1-2, ReL1-3, etc].

The next chapter, Chapter XI, only presents some ideas for ac- cessing the symmetric census of maps and further, of graphs. This topic is being developed in some other directions|KwL1-2] and left as a subject written in the near future.

From Chapter XII through Chapter XV, extensions from basic theory are much concerned with further applications.

Chapter XII discusses in brief on genus polynomial of a graph and all its super maps rooted and unrooted on the basis of the joint tree model. Recent progresses on this aspect are referred to read the articles [Liu13-15, LiP1, WaL1-2, ZhL1-2, ZuL1, etc].

Chapter XIII is on the census of maps with vertex or face par- titions. Although such census involves with much complication and difficulty, because of the recent progress on a basic topic about trees via an elementary method firstly used by the author himself we are able to do a number of types of such census in very simple way. This chapter reflects on such aspects around.

Chapter XIV is on graphs that their super maps are particularly considered for asymmetrical and symmetrical census via their semi- automorphism and automorphism groups or via embeddings of graphs given [Liu19, MaL1, MaT1, MaW1, etc].

Chapter XV, is on functional equations discovered in the census of a variety of maps on sphere and general surfaces. Although their

vi Preface

well definedness has been done, almost all of them have not yet been solved up to now.

Three appendices are compliment to the context. One provides the clarification of the concepts of polyhedra, surfaces, embeddings, and maps and their relationship. The other two are for exhaustively calculating numerical results and listing all rooted and unrooted maps for small graphs with more calculating results compared with those appearing in [Liu14], |Liu17] and |Liu19].

From a large amount of materials, more than hundred observa- tions for beginners probably senior undergraduates, more than hun- dred exercises for mainly graduates of master degree and more than hundred research problems for mainly graduates of doctoral degree are carefully designed at the end of each chapter in adapting the needs of such a wide range of readers for mastering, extending and investigat- ing a number of ways to get further development on the basic theory of abstract maps.

Although I have been trying to design this book self contained as much as possible, some books such as [DiM1], [Mss1] and [GaJ1] might be helpful to those not familiar with basic knowledge of permutation groups, topology and computing complexity as background.

Since early nineties of the last century, a number of my former and present graduates were or are engaged with topics related to this book. Among them, I have to mention Dr. Ying Liu[LpL1], Dr. Yuan- qiu Huang[|HuL1], Dr. Junliang Cai[CaL1-2], Dr. Deming Li|LiL1], Dr. Han Ren[ReL1-3], Dr. Rongxia Hao[HaC1, HaL1], Dr. Zhaox- iang Li|LiQ1-2], Dr. Linfan Mao|MaL1, MaT1, MaW1], Dr. Er- ling Wei[WiL1-2], Dr. Weili He[HeL1], Dr. Liangxia Wan[WaL1-2], Dr. Yichao Chen|CnL1, CnR1], Dr. Yan Xu|XuL1-2], Dr. Wen- zhong Liu[LwL1-2]|, Dr. Zeling Shao[ShL1], Dr. Yan Yang[YaL1-2], Dr. Guanghua Dong{DoL1], Ms. Ximei Zhao[ZhL1-2], Mr. Lifeng Li[LiP1], Ms. Huiyan Wang[WgL1], Ms. Zhao Chai[CiL1], Mr. Zi- long Zhu[ZuL1], et al for their successful work related to this book.

On this occasion, I should express my heartiest appreciation of the financial support by KOSEF of Korea from the Com?MaC (Com-

Preface vu

binatorial and Computational Mathematics Research Center) of the Pohang University of Science and Technology in the summer of 2001. In that period, the intention of this book was established. Moreover, I should be also appreciated to the Natural Science Foundation of China for the research development reflected in this book under its Grants(60373030, 10571013, 10871021).

Y.P. Liu Beijing, China Jan., 2010


POAC. ca scc eames ENVIO o aM UpR NEUEN EDU a RS iii Chapter I Abstract Embeddings ............................ 1 [I.1 Graphs and networks use a a ag ace xr aC cb doin atrae dea ce a os 1

L2 AG MERMTTT-—-——————— 9 iin Cds 25 s68 eer ien t duri dod bb 16

1.4 Abstract representation ............ 0.00 ccc cece e nee 22

L5 Smarandache 2-manifolds with map geometry ......... 27 Activities on Chapter I .............................sess 32

D5 Observations used Cao ater ido c aac eae aca edd ce c a 32

Er D e E E E E E 34

IS Reséearchês:srirssecrsisriisirrid Cada bed OR pound 37 Chapter II Abstract Maps ..................... 00 cee eee eee Al [ll Ground S016. eras e rdeda ive ane an iaiia euet dx 41

I2 Basi permutations essesi qaa Y asit ede d abe daa dara 43

[I.3 Conjugate BIO. oo a9 RO au Que ROPA ag RR 46


IL5 Included angles.. n... qu schemi ca ide ro ata? enrich 55 Activities on Chapter II ................................ 57

[I.6 Observations. tet atias.ose eae eni at dar datio eed ad eee taree 57

WD ee hee atu et ee went TTE E I TOI TT TT 58

ILS ResearchESeereeisreredenionit ernaia na eta oy Eia 59 Chapter III Duality .s.cucidese eases lotti hr o XCR e CR eoe d 65

DELI Dual DS senesini anene tbi ru ade arsit ad padre RA 65

X Contents

II.2 Deletion of an edge us uomexexa xu erae ed d a x eb a redes 72

TILES Addition of an CACC. 16.20. deGeeuktewdetetideauatadadd 85

HIA Basie transformati oss siniesigivastacegaesatxnadeeaw’ 96 Activities on Chapter III ............................se. 98 [II.5 Observations. uc daa s tin prt n a qitod Sr da Oa ora 98

ILU EXErCigES s sodatn Exe E RM vd sees Red Padi vd 99

[HT TRGSOREC DO e erscinas quac tanya dee dp ac opui a vay det 101 Chapter IV Orientability .......................Lsssessss 103 IN d Ornéntation ua sica aca don at Fo a deb S fec rae t har 103

1352 Basic GuivaleliCeus s quem aua t ri o Redon he 30 9 ae cay 107

IS 9 Euler characteristic ssa eene Sa a epe RX eadavassdea cs 113

IV.4 Pattern examples ssa inane aan eave SO OR RR) 116 Activities on Chapter IV ...........................s. 119 Es QC NEST T ET OE OT 119

T5. Exercises ote ries dui ice diesen d n o oni depu m bo aa dic 120

IV rc Researches: eo cem ekle EO RC RC E CP ec e db oes 122 Chapter V Orientable Maps ....................... suse. 124 V.1 Butterflies usus tase dard i b aee RR LR eg oar rat 124

352 Simplified DubbertliQg. viua dasiooben ER ERA I eee ao does 126

Veo Reduced rules iuoaaueus d e? Vie waa nir ara q apto edad 130

V.4 Ornentable principled) order hore EC PpCOO e a 134

Veo Qrentable PONS: ziehe pda por dex Edu eoe 137 Activities on Chapter V isse ek xa rarae das 139

V.6 Observations Lia auis cte dot eoo herd eet tul 139

Quid 169 1: er araa raS a N OO OUT LOTO Dll S 140

A S Researches 5.4500 pupa ibt doce dcl opui dc ape Rice EXE LUCR 142 Chapter VI Nonorientable Maps ........................ 145


Contents xi

VI.2 Simplified DAIIOS. :scwsaeyvsdsn esaecue i aue ades xad 149 VI.3 Nonorientable rules iua ua qe iratiag ea eda ow oer as 151 VLA Nonorientable principles «usos cese mr Rs 156 VI.5 Nonorientable perius, iussi eerte e 157 Activities on Chapter VI ........................ssess 159 VI:S Observations ks aa od Race Pda ade e d rada qr ibas d 159 VLO ExerciSES PT 160 DANN. 01: Mm 162 Chapter VII Isomorphisms of Maps .................... 164 MIL EACOmiti AUIID uoces aw bolo DE Ea d acl A ODE A oto 164 VIIL.2 Isomorphism OHODPOEL, sa dai o S rea ed ea dura 168 VILS Hee ni MTM" 172 MESS Justification ecd param nha a dci ru dd RE RE ELE ew ak 177 VIL Pattern examples... ci reeacea nde rk OR P S e nian 180 Activities on Chapter VII ..........................se. 185 VIO ODSOPVOUOPIB o uada ex tod ERO bar acatecta Pars qnos 185 VIDT Ss cece usb piedad mb dez vua tite Ru acr prp ard; 186 VILS: Researches ceo zd vxo arceat XR Re xo Pici c aao 188 Chapter VIII Asymmetrization ......................... 190 VLE AG OHIOTISDESHEIS eo ee eta pha etam irt bereit tnb 190 VIIL2 Upper bound of group order............LsLssuuueuue. 193 VIIL3 Determination of the group...................000- 196 VULA ROODE S mesire minaaa usec natn ee etui dud subi 201 Activities on Chapter VIII .........................s. 206 MILL QOS VA HONS s us a in iq e Perna c epa re opa eg s 206 MILIA BISOBCISEBS s cued t dp pe VC RRPER C rc Pe Re Pee E Rs 207

ATI. F6ear hes yak esee S Roe ee acd Ren eem Eo s 209

xli Contents

Chapter IX Rooted Petal Bundles ....................... 212 IX.1 Orientable petal bundles... n.n.. Lor re 212

[IX.2 Planar pedal bundles «544» 9223 e re heard 2IT

IX.3 Nonorientable pedal bundles....................sse. 220

IX.4 The number of pedal bundles....................... 226 Activities on Chapter IX .............................. 230 [X.5 Observations. ........ ununun nananana nananana 230

[X.6 Exercises 410g Da mesi vases be dat ESE KESER ESNA NEE ERDRE Ea 231

IX. 0 Resear Chics. cessie era PX VOCE HOER VICES E SER RUP ex ra Ro 202 Chapter X Asymmetrized Maps ......................... 235 X.1 Orientable equation........... 0... cece eee nes 235

X.2 Planar rooted I DES e io pst duuybur dehet dri rrara 243

A.9 Nonorientable equation :2. 2 voor ter RE RR RR RA RR 250

X.4 Gross GuabtlOfb. v au Sog serasa saunu abes don debo OU 255

Ao The number of rooted mapa-ssese sat ex bns 258 Activities on Chapter X ............................... 261

X.6 Observations TEE 261

bm cut RRRREPR 262

X8 Researches s conc agar eta esr acl Papi Sept edic abd RR i 265 Chapter XI Maps with Symmetry ....................... 268 AL] Symmetric relation |. eovescs ones hoa E hee oO hk 268

XI An annHlcablOleessensequad rest Ibsiea ora RE E d. 270

XI.3 Symmetric principle >... cu antowy aire, dane aca acne DR 212

XI.4 General examples........... 0... cc ccc eee ee ee 274 Activities on Chapter XI .........................Lsss. 278 XI.5 CDS GB aeuo ert leger nis Ee enr Pb Ehe a d 278 RAD PRMNNCE T PITT 279

AXI T ReséarchéS. Lese wie chee deck arate a weet e Aten Po POR weld 280

Contents xiii

Chapter XII Genus Polynomials ......................... 282 AIL1 Associate surfaces 1i. cessere ert eres 282

AIL Layer division of a surface Lec o pet E v ERR 285

AL Handle polymomials 22a pide ded debo er eode 289

XII.4 Crosscap polynomials ua seien eame coun Fee ec es n 290 Activities on Chapter XII ..........................ss 292 XIL.5 Observations. bore nd ducentas pb ROS Roe RU Id dod 292

PU Gores PRINS actu anes OTI IT LITT 293

X.T CSC 001. ss sec crnctndcteenaakiensdk tated earners 294 Chapter XIII Census with Partitions .................... 297 PTL Planted trees aue dedere dace asm dida Soit cine: 297

Al 2 Hamiltonian cubic Mapes discs ee bo Le rh RR ARORAA 305

ATTE S Halin maps aereo es esie qe REA Era tog adie ele POR 307

XIIL4 Biboundary inner rooted maps ................sue 310

II General maps ce eectesce qu tad biciaces VAL CARA E aces 315

XIHI.6 Pane ean: acus acr ai ended he raton Rc p Iu weg 917 Activities on Chapter XIII ............................ 323 AIL. E TODSEPUAUIONSS osa arra ta da wires Strap e CR pro pos 323

RAULS BXGPCISOS sad queas P Eh POS na ian dator mda E E 324

AULD Researches Lu doses paca is aa xe x ORC IE OR re ecl 325 Chapter XIV Super Maps of a Graph ................... 326 XIV.1 Semi-automorphisms on a graph .................. 326

XIV.2 Automorphisms on a graph scs ovesoerriecet Ene dn 329

XIV.3 Relationships oio qd eic doe P Desc RR Ra m ORAL 332

XIV.4 Nonisomorphic super maps................00000ee- 334

XIV.5 Via rooted super MANS .2iiaacdccesnerganeascae dares 336 Activities on Chapter XIV .........................s 341

XIV .G Observallofis.l.2 26r red e Ee x esent 341

xlv Contents

PAN AC ECGs S s casses Ped y ebd e me dd Edd SE Se ds 342 XIV:8 Researches Pm 334 Chapter XV Equations with Partitions ................. 345 XV.1 The meson functional xxv esee xe ees 345 XV.2 General maps on the sphere.............Luuuuusuuus 350 XV.3 Nonseparable maps on the sphere.................. 303 XV.4 Maps without cut-edge on furfaces................. 307 XV.5 Eulerian maps on the sphere.................00000- 361 XV.6 Eulerian maps on Surfaces... acceso etre 365 Activities on Chapter XV ........................ssss. 370 XV.7 CbservatiOfigesscie ee d va e Deren Od Re ia e 370 DoW oy BOT o MMC orl beg X1 040 state ened cian ener ai he ahaoe 372

Appendix I Concepts of Polyhedra, Surfaces,

Embeddings and Maps 52 eme 374 DT Pol Waite care eae bol eae paren aE 374 Pa ees aver ono Oe owe oo eee ee 377 Ax.I.3 To DOOOLHE Sos w id dade aar Quiet go M e co ool eed 381 CY Ri PH" 384

Appendix II Table of Genus Polynomials for

Embeddings and Maps of Small Size............ 389 Ax.IL1 Triconnected cubic graphs...................00005 389 A IL2- Dot Sie xoc iocos Suc sex dea tances hoes nd eu es 398 AILES WHOIS Ss wdc cre veces pear kese EREE E RES oe 401 oe TEE Link Dultidlóges cs exercere tan caet bce ER prati e 403 Ax.IL5 Complete bipartite graphs....................0005 405

Ax.ILO Complete graphs. «ce ehe h ge teens ntn 407

Contents XV

Appendix III Atlas of Rooted and Unrooted Maps

for Small €Papligosad esses x AR aad rA ARRA 409

Ax.IIL1 Bouquets Bm of size 4> M> 1................. 409 Ax.IIL2 Link bundles Lm of size 7 > m > 3....... ees 415 Ax.IIL3 Complete bipartite graphs Km,n, 4 > m,n > 3...432

Ax. ILA Wheels W, of order 6 > n > 4... severe 437

Ax 111.5 Complete graphs Kn, 5 > m > 4... esee 447 Ax.III.6 Triconnected cubic graphs of size in [6,15]....... 452 Biblogřaphy ssuresansde s heeatenoa sis du adbn Sa du EDSR sa ad uar dtd 472

Terminology cr kiant boa OnE vp" 480

Chapter I Abstract Embeddings

e A graph is considered as a partition on the union of sets obtained from each element of a given set the binary group B = {0,1} sticks on.

e A surface, i.e., a compact 2-manifold without boundary in topol- Ogy, ls seen as a polygon of even edges pairwise identified.

e An embedding of a graph on a surface is represented by a joint tree of the graph. A joint of a graph consists of a plane extended tree with labelled cotree semi-edges. Two semi-edges of a cotree edge has the same label as the cotree edge with a binary index. An extended tree is compounded of a spanning tree with cotree semi-edges.

e Combinatorial properties of an embedding in abstraction are par- ticularly discussed for the formal definition of a map.

L1 Graphs and networks

Let X bea finite set. For any x X, the binary group B = {0,1} sticks on x to obtain Bx = {x(0), z(1)). x(0) and z(1) are called the ends of x, or Bx. If Bx is seen as an ordered set (x(0), z(1)), then

2 Chapter I Abstract Embeddings

x(0) and z(1) are, respectively, initial and terminal ends of x. Let

Ade vo Hn (1.1)


i.e., the disjoint union of all Bx, x X. X is called the ground set.

A (directed) pregraph is a partition Par= (Pi, Po, ---} of the ground set AX ,1.e.,

A= ye, (1.2) i>1

Bx (or (x(0), x(1))), or simply denoted by z itself, x X, is called an (arc) edge and P;, i > 1, a node or vertex.

A (directed) pregraph is written as G (V, E) where V —Par and

E = B(X) ={Bal|x X]

(= {(x(0), x(1))] Xj).

If X is a finite set, the (directed) pregraph is called finite; otherwise, infinite. In this book, (directed) pregraphs are all finite.

If X = Ø, then the (directed) pregraph is said to be empty as well.

An edge (arc) is considered to have two semiedges each of them is incident with only one end (semiarcs with directions of one from the end and the other to the end). An edge (arc) is with two ends identified is called a selfloop (di-selfloop); otherwise, a link (di-link). If t edges (arcs) have same ends (same direction) are called a multiedge (multiarc), or t-edge (t-arc).

Example 1.1 There are two directed pregraphs on X = (x], 1 B.

Par; = ((z(0)), {x(1) }}; Par; = {{x(0), x(1)}}.

They are all distinct pregraphs as well as shown in Fig.1.1.

L1 Graphs and networks 3

Xx T Parı Pars Fig.1.1 Directed pregraphs of 1 edge

Further, pregraphs of size 2 are observed.

Example 1.2 On X = {21,22}, the 15 directed pregraphs are as follows:

Par, = ((1(0)). 00100). {2(0)}, {z2(1)}}; Par, = {{21(0), x1(1)}, {x2(0)}, 122(1) 1: Pars = {{21(0), x2(0)}, {z1(1)}, 102(1) 1: Par, = {{21(0), xo(1)}, {z1(1)}, 122(0) 1; Pars = {{21(0)}, {21(1), £2(0)}, {za(1) 1: Pars = {{21(0)}, {21(1), 29(1) }, 122(0) 1; Par; = {{21(0)}, {21(1)}, {z2(1), z2(0)}}; Pars = {{1(0), x1(1), z2(0)}, 122(1) } }: Parg = {{1(0), 21(1), z2(1)}, 122(0) fF: Pario = {{21(0), 22(0); z2(1)}, {£1(1)}}; Pari = {{21(0)}, {21(1), %2(0), z2(1)}}; Paria = {{x1(0), 21(1), va(0), vo(1) }}; Paris = {{21(0), x1(1)}, {22(0), vo(1) 3: Paria = {{21(0), x2(0)}, {21(1), a(1) fF: Paris = {{21(0), x2(1)}, {1(1), v2(0) fF.

Among the 15 directed pregraphs, Pars, Par4, Pars; and Pare are 1 pregraph; Pars and Parg are 1 pregraph; Parjo and Par; are 1 pregraph; Par;4 and Parı5 are 1 pregraph; and others are 1 pregraph each. Thus, there are 9 pregraphs in all(as shown in Fig.1.2).

4 Chapter I Abstract Embeddings

T T y y { ] x 1 2

Par, Paro Para T2 "o we I1 T2 Par4 Pars Parę X1 V V Parz Parg Parg x L] M? I Pario Pari Parj2 x

zl 7 2i qi Paria Pari4 Paris

Fig.1.2 Directed pregraphs of 2 edges

Now, Par= (P4, Po,---} and B are, respectively, seen as a map- ping z => P, z P, i > 1 anda mapping z +> Z, Z Æ z, {z,z} B(X). The composition of two mappings a and (3 on a set Z is defined

L1 Graphs and networks 5

to be the mapping (aß)z = U ay, z Z. (1.3)


Let Vypargy be the semigroup generated by Par=Par(X) and B = B(X). Since the mappings a =Par and B have the property that y az & z ay, it can be checked that for any z, y B(X), what is determined by dy Vipargy, 2 vy

is an equivalence. If B( X) itself is a equivalent class, then the semi- group V (pa; g} is called transitive on X' = B(X). A (directed)pregraph with V pag transitive on X is called a (directed ) graph .

A (directed)pregraph G = (V, E) that for any two vertices u,v V, there exists a sequence of edges e1, €2,---,e, for the two ends of e;, i = 2,3,---,s—1, are in common with those of respective e;_; and e;44 where u and v are, respectively, the other ends of e; and eg, is called connected . Such a sequence of edges is called a trail between u and v. A trail without edge repetition is a walk. A walk without vertex repetition is a path. A trail, walk, or path with u = v is, respectively, a travel, tour, or circuit.

Theorem 1.1 A (directed)pregraph is a (directed)graph if, and only if, it is connected.

Proof Necessity. Since Par’ = Par, k > 1, and B* = B, k > 1, by the transitivity, for any two elements y, z X, there exists y such that z yy and there exists an integer n > 0 such that

y = (BPar)" B = (BPar) --- (BPar) B, (1.4)


where BPar appears for n times. Therefore, the (directed)pregraph is connected.

Sufficiency. If a (directed)pregraph is connected, i.e., for any two elements x,y X, their incident vertices u,v V, have edges e1, €2,°°*,@s, Such that e;, 2 = 2,83,---,s5— 1, is in common with e;. 4

6 Chapter I Abstract Embeddings

and e;4,1. Of course, u and v are, respectively, the ends of e1 and es. Thus, y yz wherey (ParB)?B. This implies that the semigroup V,parg; is transitive on A. Therefore, the (directed)pregraph is a (directed)graph. O

It is seen from the theorem that (directed) graphs here are, in fact, connected (directed) graphs in most textbooks. Because discon- nectedness is rarely necessary to consider, for convenience all graphs, embeddings and then maps in what follows are defined within con- nectedness in this book.

A network N is such a graph G = (V, E) with a real function w(e) R,e E on E, and hence write N = (G;w). Usually, a network N is denoted by the graph G itself if no confusion occurs.

Finite recursion principle On a finite set A, choose ag A as the initial element at the Oth step. Assume a; is chosen at the ith, i > 0, step with a given rule. If not all elements available from a; are not yet chosen, choose one of them as a;,4, at the i+ 1st step by the rule, then a chosen element will be encountered in finite steps unless all elements of A are chosen.

Finite restrict recursion principle Ona finite set A, choose ag A as the initial element at the Oth step. Assume a; is chosen at the ith, 2 > 0, step with a given rule. If a; is not available from aj, choose one of elements available from a; as a;,4 at the i + Ist step by the rule, then ap will be encountered in finite steps unless all elements of A are chosen.

The two principles above are very useful in finite sets, graphs and networks, even in a wide range of combinatorial optimizations.

A G = (V, E) with V = Vi + V2 of both V; and Vz independent, i.e., its vertex set is partitioned into two parts with each part having no pair of vertices adjacent, is called bipartite.

Theorem 1.2 A graph G = (V, E) is bipartite if, and only if, G has no circuit with odd number of edges.

Proof Necessity. Since G is bipartite, start from vy V ini-

L1 Graphs and networks 7

tially chosen and then by the rule from the vertex just chosen to one of its adjacent vertices via an edge unused and then marked by used, according to the finite recursion principle, an even circuit (from bipar- tite), or no circuit at all, can be found. From the arbitrariness of vo and the way going on, no circuit of G is with odd number of edges. Sufficiency. Since all circuits are even, start from marking an arbitrary vertex by 0 and then by the rule from a vertex marked by b B = {0,1} to mark all its adjacent vertices by b = 1 b, according to the finite recursion principle the vertex set is partitioned into Vo = (v V| marked by 0} and V; = (v V| marked by 1}. By the rule, Vy and Vj are both independent and hence G is bipartite. L

From this theorem, a graph without circuit is bipartite. In fact, from the transitivity, any graph without circuit is a tree.

On a pregraph, the number of elements incident to a vertex is called the degree of the vertex. A pregraph of all vertices with even degree is said to be even . If an even pregraph is a graph, then it is called a Euler graph.

Theorem 1.3 A pregraph G = (V, E) is even if, and only if, there exist circuits C1, C5, --- , C4, on G such that

E-Ci tC» C, (1.5)

where n is a nonnegative integer.

Proof Necessity. Since all the degrees of vertices on G are even, any pregraph obtained by deleting the edges of a circuit from G is still even. From the finite recursion principle, there exist a nonnegative integer n and circuits Ci, C5, --- , Cn, on G such that (1.5) is satisfied.

Sufficiency. Because a circuit contributes 2 to the degree of each of its incident vertices, (1.5) guarantees each of vertices on G has even degree. Hence, G is even. []

The set of circuits (C;|1l i n} of G in (1.5) is called a circuit partition, or written as Cir=Cir(G). Two direct conclusions of Theorem 1.3 are very useful . One is the case that G is a graph. The

8 Chapter I Abstract Embeddings

other is for G is a directed pregraph. Their forms and proofs are left for the reader.

Let N (G;w) be a network where G (V, E) and w(e) —w(e) Zn = (0,1,---,n 1}, ie., mod n, n > 1, integer group. For examples, = {0}, = B = {0,1} etc. Suppose x, = —z, Zn, v V, are variables. Let us discuss the system of equations

Eu + £y = w(e) (mod n), e = (uv) E (1.6)

On Zn.

Theorem 1.4 System of equations(1.6) has a solution on Z, if, and only if, there is no circuit C such that

X wle) ) £0 (mod n) (1.7)

ecC on N.

Proof Necessity. Assume C is a circuit satisfying (1.7) on N. Because the restricted part of (1.6) on C has no solution, the whole system of equations (1.6) has to be no solution either. Therefore, N has no such circuit. This is a contradiction to the assumption

Sufficiency. Let £o = a Zn, start from vg V reached. Assume vi V reached and x; = a; at step i. Choose one of e; = (vi, vi41) E without used(otherwise, backward 1 step as the step i). Choose v;+1 reached and e; used with a;,, = a; + w(e;) at step i + 1. If a circuit as {e€9,€1,---, e, ej = (vj, Uj41),0 j lvi = vo, occurs within a permutation of indices, then from (1.7)

Qj41 = aj + w(ei) = a1 + wle) + wle)

I.2 Surfaces 9

Because the system of equations obtained by deleting all the equations for all the edges on the circuit from (1.6) is equivalent to the original system of equations (1.6), in virtue of the finite recursion principle a solution of (1.6) can always be extracted . O

When n = 2, this theorem has a variety of applications. In [Liu5], some applications can be seen. Further, its extension on a nonAbelian group can also be done while the system of equations are not yet linear but quadratic.

1.2 Surfaces

In topology, a surface is a compact 2-dimensional manifold with- out boundary. In fact, it can be seen as what is obtained by identifying each pair of edges on a polygon of even edges pairwise.

For example, in Fig.1.3, two ends of each dot line are the same point. The left is a sphere, or the plane when the infinity is seen as a point. The right is the projective plane. From the symmetry of the sphere, a surface can also seen as a sphere cutting off a polygon with pairwise edges identified.

The two surfaces in Fig.1.3 are formed by a polygon of two edges pairwise as a.

Sphere(Plane) Projective plane

Fig.1.3 Sphere and projective plane

10 Chapter I Abstract Embeddings

Surface closed curve axiom A closed curve on a surface has one of the two possibilities: one side and two sides.

A curve with two sides is called a double side curve ; otherwise, a single side curve . As shown in Fig.1.3, any closed curve on a sphere is a double side curve(In fact, this is the Jordan curve axiom). However, it is different from the sphere for the projective plane. there are both a single(shown by a dot line) and a double side curve.

How do we justify whether a closed curve on a surface is of single side, or not?

In order to answer this question, the concept of contractibility of a curve has to be clarified. If a closed curve on a surface can be continuously contracted along one side into a point, then it is said to be contractible, or homotopic to 0.

Torus Klein bottle

Fig.1.4 Torus and Klein bottle

It is seen that a single side curve is never homotopic to 0 and a double side curve is not always homotopic to 0. For example, in Fig.1.4, the left, i.e., the torus, each of the dot lines is of double side but not contractible. The right, i.e., the Klein bottle, all the dot lines are of single side , and hence, none of them is contractible.

A surface with all closed curves of double side is called orientable; otherwise, nonorientable .

For example, in Fig.1.3, the sphere is orientable and the projec-

I.2 Surfaces 11

tive plane is nonorientable. In Fig.1.4, the torus is orientable and the Klein bottle is nonorientable.

The maximum number of closed curves cutting along without destroying the continuity on a surface is called the pregenus of the surface.

In view of Jordan curve axiom, there is no such closed curve on the sphere. Thus, the pregenus of sphere is 0. On the projective plane, only one such curve is available (each of dot lines is such a closed curve in Fig.1.3) and hence the pregenus of projective plane is 1.

Similarly, the pregenera of torus and Klein bottle are both 2 as shown in Fig.1.4.

Theorem 1.5 The pregenus of an orientable surface is a non- negative even number.

A formal proof can not be done until Chapter 5. Based on this theorem, the genus of an orientable surface can be defined to be half its pregenus, called the orientable genus. The genus of a nonorientable surface, called nonorientable genus, is its pregenus itself.

The sphere is written as aa^! where a^! is with the opposite direction of a on the boundary of the polygon. Thus, the projective plane, torus and Klein bottle are, respectively, aa, aba~!b~! and aabb. In general,

p Op = ajbja; b7 | l T = abia bi lasboa; b3 - . aybya;, b; ! and q Qe = li Aili = 41010202 * ` AgAg (1.9)

i=l denote, respectively, a surface of orientable genus p and a surface of nonorientable genus q. Of course, Oo, Q1, O1 and are, respectively, the sphere, projective plane, torus and Klein bottle.

It is easily checked that whenever an even polygon is with a pair of its edges in the same direction, the polygon represents a nonori-

12 Chapter I Abstract Embeddings

entable surface. Thus, all Op, p > 0, orientable and all Q,, q = 1, are nonorientable.

Forms (1.8) and (1.9) are said to be standard.

If the form of a surface is defined by its orientability and its genus, then the operations 1-3 and their inverses shown as in Fig.1.5-7, do not change the surface form.

Fig.1.5 Operation 1: Aaa | < A

Fig.1.6 Operation 2: AabBab < AcBc

Fig.1.7 Operation 3: AB 4 ( (Aa)( a 1B)

In fact, what is determined under these operations is just a topo- logical equivalence, denoted by ~top.

Notice that A and B are all linear order of letters and permitted

I.2 Surfaces 13

to be empty as degenerate case in these operations. 'The parentheses stand for cyclic order when more than one cyclic orders occur for distinguishing from one to another.

Relation 0 On a surface (A, B), if A is a surface itself then (A, B) = ((A)z(B)z 7) = ((A)(B)).

Relation 1 (AxByCaz !Dy )) ~top ((ADCB)(zxyr |y !)).

Relation 2 (AzBz) ^y ((AB™')(xz)).

Relation 3 (Axzyzy !z |) ~top ((A)(zx)(yy)(zz)).

In the four relations, A, B, C, and D are permitted to be empty. B^ = b7! . -b3 'b7'b7' is also called the inverse of B = bibob3 - - bs,

s > 1. Parentheses are always omitted when unnecessary to distin- guish cyclic or linear order.

On a surface S, the operation of cutting off a quadrangle aba! 57! and then identifying each pair of edges with the same letter is called a handle as shown in the left of Fig.1.8.

If the quadrangle aba~!b~! is replaced by aa, then such an oper- ation is called a crosscap as shown in the right of Fig.1.8.

Handle Crosscap

Fig.1.8 Handle and crosscap

The following theorem shows the result of doing a handle on an orientable surface.

Theorem 1.6 What is obtained by doing a handle on an ori- entable surface is still orientable with its genus 1 added.

14 Chapter I Abstract Embeddings

Proof Suppose S is the surface obtained, then

p B ovs | [ a0; 5; cap ibat! ( Relation 0) i=1 p pad. si aed ; ~top ] [aio b; xx 0ga55185,115,5, (Relation 1) i=1 p eis EET ^" top ] [ aita; b; Qp410p 4105 10544 (Operation 1) i1 p+1

= li ajbja; ^b; |. i=l

This is the theorem. []

In the above proof, x and x! are a line connecting the two

boundaries to represent the surface as a polygon shown in Fig.1.8. 'This procedure can be seen as the degenerate case of operation 3.

In what follows, observe the result by doing a crosscap on an orientable surface.

Theorem 1.7 Onan orientable surface of genus p, p > 0, what is obtained by doing a crosscap is nonorientable with its genus 2p + 1.

Proof Suppose N is the surface obtained, then

p N Step li a;bia; |b; xaax | (Relation 0)