Algebraic Elements of Graphs

by Yanpei Liu, University of Science and Technology China Press (Contribution by)

Overview

This book studies algebraic representations of graphs in order to investigate combinatorial structures via local symmetries. Topological, combinatorial and algebraic classifications are distinguished by invariants of polynomial type and algorithms are designed to determine all such classifications with complexity analysis. Being a summary of the author‘s original work on graph embeddings, this book is an essential reference for researchers in graph theory.

Contents
Abstract Graphs
Abstract Maps
Duality
Orientability
Orientable Maps
Nonorientable Maps
Isomorphisms of Maps
Asymmetrization
Asymmetrized Petal Bundles
Asymmetrized Maps
Maps within Symmetry
Genus Polynomials
Census with Partitions
Equations with Partitions
Upper Maps of a Graph
Genera of a Graph
Isogemial Graphs
Surface Embeddability

Product Details

ISBN-13:	9783110480757
Publisher:	De Gruyter
Publication date:	09/11/2017
Sold by:	Barnes & Noble
Format:	eBook
Pages:	422
File size:	15 MB
Note:	This product may take a few minutes to download.
Age Range:	18 Years

About the Author

Yanpei Liu, Beijing Jiaotong University, Beijing, China

Table of Contents

1 Abstract Graphs 1

1.1 Graphs and networks 1

1.2 Surfaces 7

1.3 Embedding 12

1.4 Abstract representation 16

1.5 Notes 22

2 Abstract Maps 26

2.1 Ground sets 26

2.2 Basic permutations 27

2.3 Conjugate axiom 30

2.4 Transitive axiom 33

2.5 Included angles 35

2.6 Notes 38

3 Duality 43

3.1 Dual maps 43

3.2 Deletion of an edge 49

3.3 Addition of an edge 59

3.4 Basic transformation 67

3.5 Notes 68

4 Orientability 70

4.1 Orientation 70

4.2 Basic equivalence 73

4.3 Euler characteristic 78

4.4 Pattern examples 81

4.5 Notes 83

5 Orientable Maps 85

5.1 Butterflies 85

5.2 Simplified butterflies 86

5.3 Reduced rules 89

5.4 Orientable principles 94

5.5 Orientable genus 96

5.6 Notes 97

6 Nonorientable Maps 100

6.1 Barflies 100

6.2 Simplified barflies 103

6.3 Nonorientable rules 105

6.4 Nonorientable principles 109

6.5 Nonorientable genus 110

6.6 Notes 111

7 Isomorphisms of Maps 113

7.1 Commutativity 113

7.2 Isomorphism theorem 117

7.3 Recognition 120

7.4 Justification 123

7.5 Pattern examples 125

7.6 Notes 130

8 Asymmetrlzation 132

8.1 Automorphisms 132

8.2 Upper bounds of group order 135

8.3 Determination of the group 137

8.4 Rootings 141

8.5 Notes 145

9 Asymmetrized Petal Bundles 147

9.1 Orientable petal bundles 147

9.2 Planar pedal bundles 151

9.3 Nonorientable pedal bundles 154

9.4 The number of pedal bundles 159

9.5 Notes 161

10 Asymmetrized Maps 165

10.1 Orientable equation 165

10.2 Planar rooted maps 171

10.3 Nonorientable equation 177

10.4 Gross equation 181

10.5 The number of rooted maps 184

10.6 Notes 186

11 Maps within Symmetry 188

11.1 Symmetric relation 188

11.2 An application 189

11.3 Symmetric principle 191

11.4 General examples 192

11.5 Notes 195

12 Genus Polynomials 197

12.1 Associate surfaces 197

12.2 Layer division of a surface 199

12.3 Handle polynomials 202

12.4 Crosscap polynomials 203

12.5 Notes 204

13 Census with Partitions 207

13.1 Planted trees 207

13.2 Hamiltonian cubic map 214

13.3 Halin maps 215

13.4 Biboundary inner rooted maps 218

13.5 General maps 221

13.6 Pan-flowers 223

13.7 Notes 227

14 Equations with Partitions 230

14.1 The meson functional 230

14.2 General maps on the sphere 234

14.3 Nonseparable maps on the sphere 237

14.4 Maps without cut-edge on surfaces 240

14.5 Eulerian maps on the sphere 244

14.6 Eulerian maps on the surfaces 247

14.7 Notes 250

15 Upper Maps of a Graph 253

15.1 Semi-automorphisms on a graph 253

15.2 Automorphisms on a graph 256

15.3 Relationships 257

15.4 Upper maps with symmetry 259

15.5 Via asymmetrized upper maps 261

15.6 Notes 264

16 Genera of a Graph 267

16.1 Recursion theorem 267

16.2 Maximum genus 268

16.3 Minimum genus 271

16.4 Average genus 274

16.5 Thickness 280

16.6 Interlacedness 282

16.7 Notes 284

17 Isogemial Graphs 286

17.1 Basic concepts 286

17.2 Two operations 286

17.3 Isogemial theorem 288

17.4 Non-isomorphic isogemial graphs 290

17.5 Notes 294

18 Surface Embeddability 297

18.1 Via tree-travels 297

18.2 Via homology 306

18.3 Via joint trees 310

18.4 Via configurations 316

18.5 Notes 322

Appendix 1 Concepts of Polyhedra, Surfaces, Embeddings and Maps 325

A1.1 Polyhedra 325

A1.2 Surfaces 327

A1.3 Embeddings 331

A1.4 Maps 333

Appendix 2 Table of Genus Polynomials for Embeddings and Maps of Small Size 336

A2.1 Triconnected cubic graphs 336

A2.2 Bouquets 344

A2.3 Wheels 346

A2.4 Link bundles 347

A2.5 Complete bipartite graphs 349

Appendix 3 Atlas of Rooted and Unrooted Maps for Small Graphs 351

A3.1 Bouquets B_m of size 4 ≥ m ≥ 1 351

A3.2 Link bundles L_m, 6 ≥ m ≥ 3 356

A3.3 Complete bipartite graphs K_m,n, 4 ≥ m, n ≥ 3 367

A3.4 Wheels W_n, 5 ≥ n ≥ 4 372

A3.5 Triconnected cubic graphs of size in [6, 15] 375

Bibliography 395

Author Index 403

Subject Index 405

Editorial Reviews

Table of Content:
Preface
Chapter 1 Abstract Graphs
1.1 Graphs and Networks
1.2 Surfaces
1.3 Embeddings
1.4 Abstract Representation
1.5 Notes
Chapter 2 Abstract Maps
2.1 Ground Sets
2.2 Basic Permutations
2.3 Conjugate Axiom
2.4 Transitive Axiom
2.5 Included Angles
2.6 Notes
Chapter 3 Duality
3.1 Dual Maps
3.2 Deletion of an Edge
3.3 Addition of an Edge
3.4 Basic Transformation
3.5 Notes
Chapter 4 Orientability
4.1 Orientation
4.2 Basic Equivalence
4.3 Euler Characteristic
4.4 Pattern Examples
4.5 Notes
Chapter 5 Orientable Maps
5.1 Butterflies
5.2 Simplified Butterflies
5.3 Reduced Rules
5.4 Orientable Principles
5.5 Orientable Genus
5.6 Notes
Chapter 6 Nonorientable Maps
6.1 Barflies
6.2 Simplified Barflies
6.3 Nonorientable Rules
6.4 Nonorientable Principles
6.5 Nonorientable Genus
6.6 Notes
Chapter 7 Isomorphisms of Maps
7.1 Commutativity
7.2 Isomorphism Theorem
7.3 Recognition
7.4 Justification
7.5 Pattern Examples
7.6 Notes
Chapter 8 Asymmetrization
8.1 Automorphisms
8.2 Upper Bounds of Group Order
8.3 Determination of the Group
8.4 Rootings
8.5 Notes
Chapter 9 Asymmetrized Petal Bundles
9.1 Orientable Petal Bundles
9.2 Planar Pedal Bundles
9.3 Nonorientable Pedal Bundles
9.4 The Number of Pedal Bundles
9.5 Notes
Chapter 10 Asymmetrized Maps
10.1 Orientable Equation
10.2 Planar Rooted Maps
10.3 Nonorientable Equation
10.4 Gross Equation
10.5 The Number of Rooted Maps
10.6 Notes
Chapter 11 Maps Within Symmetry
11.1 Symmetric Relation
11.2 An Application
11.3 Symmetric Principle
11.4 General Examples
11.5 Notes
Chapter 12 Genus Polynomials
12.1 Associate Surfaces
12.2 Layer Division of a Surface
12.3 Handle Polynomials
12.4 Crosscap Polynomials
12.5 Notes
Chapter 13 Census with Partitions
13.1 Planted Trees
13.2 Hamiltonian Cubic Maps
13.3 Halin Maps
13.4 Biboundary Inner Rooted Maps
13.5 General Maps
13.6 Pan-Flowers
13.7 Notes
Chapter 14 Equations with Partitions
14.1 The Meson Functional
14.2 General Maps on the Sphere
14.3 Nonseparable Maps on the Sphere
14.4 Maps Without Cut-Edge on Surfaces
14.5 Eulerian Maps on the Sphere
14.6 Eulerian Maps on Surfaces
14.7 Notes
Chapter 15 Upper Maps of a Graph
15.1 Semi-Automorphisms on a Graph
15.2 Automorphisms on a Graph
15.3 Relationships
15.4 Upper Maps with Symmetry
15.5 Via Asymmetrized Upper Maps
15.6 Notes
Chapter 16 Genera of Graphs
16.1 A Recursion Theorem
16.2 Maximum Genus
16.3 Minimum Genus
16.4 Average Genus
16.5 Thickness
16.6 Interlacedness
16.7 Notes
Chapter 17 Isogemial Graphs
17.1 Basic Concepts
17.2 Two Operations
17.3 Isogemial Theorem
17.4 Nonisomorphic Isogemial Graphs
17.5 Notes
Chapter 18 Surface Embeddability
18.1 Via Tree-Travels
18.2 Via Homology
18.3 Via Joint Trees
18.4 Via Configurations
18.5 Notes
Appendix 1 Concepts of Polyhedra, Surfaces, Embeddings and Maps
Appendix 2 Table of Genus Polynomials for Embeddings and Maps of Small Size
Appendix 3 Atlas of Rooted and Unrooted Maps for Small Graphs
Bibliography

From the Publisher