Topological Graph Theory

by Gross, Jonathan L.; Tucker, Thomas W.

• ISBN13: 9780486417417
• ISBN10: 0486417417
• Edition: Reprint
• Format: Paperback
• Copyright: 2012-07-17
• Publisher: Dover Publications

Summary

This introduction emphasizes graph imbedding but also covers the connections between topological graph theory and other areas of mathematics. Authors explore the role of voltage graphs in the derivation of genus formulas, explain the Ringel-Youngs theorem and examine the genus of a group, including imbeddings of Cayley graphs. 1987 edition. Many figures.

Author Biography

Jonathan L. Gross is Professor of Computer Science at Columbia University. His research in topology, graph theory, and cultural sociometry has resulted in a variety of fellowships and research grants.

Thomas W. Tucker is Mathematics Professor at Colgate University. His research interests include topology, group theory, and combinatorics.

Table of Contents

Introduction	p. 1
Representation of graphs	p. 1
Drawings	p. 2
Incidence matrix	p. 3
Euler's theorem on valence sum	p. 3
Adjacency matrix	p. 4
Directions	p. 4
Graphs, maps, isomorphisms	p. 5
Automorphisms	p. 6
Exercises	p. 7
Some important classes of graphs	p. 7
Walks, paths, and cycles; connectedness	p. 8
Trees	p. 8
Complete graphs	p. 10
Cayley graphs	p. 10
Bipartite graphs	p. 14
Bouquets of circles	p. 15
Exercises	p. 15
New graphs from old	p. 16
Subgraphs	p. 16
Topological representations, subdivisions, graph homeomorphisms	p. 17
Cartesian products	p. 19
Edge-complements	p. 19
Suspensions	p. 20
Amalgamations	p. 20
Regular quotients	p. 21
Regular coverings	p. 22
Exercises	p. 23
Surfaces and imbeddings	p. 24
Orientable surfaces	p. 24
Nonorientable surfaces	p. 25
Imbeddings	p. 26
Euler's equation for the sphere	p. 27
Kuratowski's graphs	p. 28
Genus of surfaces and graphs	p. 29
The torus	p. 30
Duality	p. 31
Exercises	p. 32
More graph-theoretic background	p. 33
Traversability	p. 34
Factors	p. 35
Distance, neighborhoods	p. 36
Graphs colorings and map colorings	p. 37
Edge operations	p. 38
Algorithms	p. 40
Connectivity	p. 40
Exercises	p. 41
Planarity	p. 42
A nearly complete sketch of the proof	p. 42
Connectivity and region boundaries	p. 45
Edge contraction and connectivity	p. 46
Planarity theorems for 3-connected graphs	p. 48
Graphs that are not 3-connected	p. 49
Algorithms	p. 51
Kuratowski graphs for higher genus	p. 53
Other planarity criteria	p. 53
Exercises	p. 54
Voltage Graphs and Covering Spaces	p. 56
Ordinary voltages	p. 57
Drawings of voltage graphs	p. 57
Fibers and the natural projection	p. 60
The net voltage on a walk	p. 61
Unique walk lifting	p. 62
Preimages of cycles	p. 63
Exercises	p. 64
Which graphs are derivable with ordinary voltages?	p. 66
The natural action of the voltage group	p. 66
Fixed-point free automorphisms	p. 67
Cayley graphs revisited	p. 69
Automorphism groups of graphs	p. 70
Exercises	p. 71
Irregular covering graphs	p. 72
Schreier graphs	p. 73
Relative voltages	p. 74
Combinatorial coverings	p. 75
Most regular graphs are Schreier graphs	p. 78
Exercises	p. 79
Permutation voltage graphs	p. 81
Constructing covering spaces with permutations	p. 81
Preimages of walks and cycles	p. 82
Which graphs are derivable by permutation voltages?	p. 84
Identifying relative voltages with permutation voltages	p. 85
Exercises	p. 86
Subgroups of the voltage group	p. 86
The fundamental semigroup of closed walks	p. 87
Counting components of ordinary derived graphs	p. 89
The fundamental group of a graph	p. 92
Contracting derived graphs onto Cayley graphs	p. 92
Exercises	p. 93
Surfaces and Graph Imbeddings	p. 95
Surfaces and simplicial complexes	p. 95
Geometric simplicial complexes	p. 96
Abstract simplicial complexes	p. 97
Triangulations	p. 98
Cellular imbeddings	p. 100
Representing surfaces by polygons	p. 102
Pseudosurfaces and block designs	p. 104
Orientations	p. 106
Stars, links, and local properties	p. 106
Exercises	p. 107
Band decompositions and graph imbeddings	p. 109
Band decomposition for surfaces	p. 109
Orientability	p. 110
Rotation systems	p. 112
Pure rotation systems and orientable surfaces	p. 113
Drawings of rotation systems	p. 113
Tracing faces	p. 114
Duality	p. 116
Which 2-complexes are planar?	p. 117
Exercises	p. 118
The classification of surfaces	p. 119
Euler characteristic relative to an imbedded graph	p. 121
Invariance of Euler characteristic	p. 121
Edge-deletion surgery and edge sliding	p. 124
Completeness of the set of orientable models	p. 126
Completeness of the set of nonorientable models	p. 128
Exercises	p. 130
The imbedding distribution of a graph	p. 132
The absence of gaps in the genus range	p. 133
The absence of gaps in the crosscap range	p. 134
A genus-related upper bound on the crosscap number	p. 136
The genus and crosscap number of the complete graph K[subscript 7]	p. 137
Some graphs of crosscap number 1 but arbitarily large genus	p. 140
Maximum genus	p. 142
Distribution of genus and face sizes	p. 146
Exercises	p. 147
Algorithms and formulas for minimum imbeddings	p. 149
Rotation-system algorithms	p. 149
Genus of an amalgamation	p. 150
Crosscap number of an amalgamation	p. 154
The White-Pisanski imbedding of a cartesian product	p. 155
Genus and crosscap number of cartesian products	p. 158
Exercises	p. 160
Imbedded Voltage Graphs and Current Graphs	p. 162
The derived imbedding	p. 162
Lifting rotation systems	p. 162
Lifting faces	p. 163
The Kirchhoff Voltage Law	p. 166
Imbedded permutation voltage graphs	p. 166
Orientability	p. 167
An orientability test for derived surfaces	p. 170
Exercises	p. 172
Branched coverings of surfaces	p. 174
Riemann surfaces	p. 174
Extension of the natural covering projection	p. 176
Which branch coverings come from voltage graphs?	p. 177
The Riemann-Hurwitz equation	p. 179
Alexander's theorem	p. 179
Exercises	p. 181
Regular branched coverings and group actions	p. 182
Groups acting on surfaces	p. 182
Graph automorphisms and rotation systems	p. 184
Regular branched coverings and ordinary imbedded voltage graphs	p. 186
Which regular branched coverings come from voltage graphs?	p. 187
Applications to group actions on the surface S[subscript 2]	p. 189
Exercises	p. 190
Current graphs	p. 191
Ringel's generating rows for Heffter's schemes	p. 191
Gustin's combinatorial current graphs	p. 193
Orientable topological current graphs	p. 194
Faces of the derived graph	p. 196
Nonorientable current graphs	p. 198
Exercises	p. 201
Voltage-current duality	p. 202
Dual directions	p. 202
The voltage graph dual to a current graph	p. 204
The dual derived graph	p. 206
The genus of the complete bipartite graph K[subscript m, n]	p. 210
Exercises	p. 212
Map Colorings	p. 215
The Heawood upper bound	p. 216
Average valence	p. 216
Chromatically critical graphs	p. 217
The five-color theorem	p. 219
The complete-graph imbedding problem	p. 220
Triangulations of surfaces by complete graphs	p. 223
Exercises	p. 224
Quotients of complete-graph imbeddings and some variations	p. 224
A base imbedding for orientable case 7	p. 225
Using a coil to assign voltages	p. 226
A current-graph perspective on case 7	p. 229
Orientable case 4: doubling 1-factors	p. 230
About orientable cases 3 and 0	p. 233
Exercises	p. 235
The regular nonorientable cases	p. 236
Some additional tactics	p. 236
Nonorientable current graphs	p. 237
Nonorientable cases 3 and 7	p. 238
Nonorientable case 0	p. 239
Nonorientable case 4	p. 240
About nonorientable cases 1, 6, 9, and 10	p. 240
Exercises	p. 240
Additional adjacencies for irregular cases	p. 241
Orientable case 5	p. 241
Orientable case 10	p. 242
About the other orientable cases	p. 245
Nonorientable case 5	p. 246
About nonorientable cases 11, 8, and 2	p. 247
Exercises	p. 247
The Genus of a Group	p. 249
The genus of abelian groups	p. 249
Recovering a Cayley graph from any of its quotients	p. 250
A lower bound for the genus of most abelian groups	p. 254
Constructing quadrilateral imbeddings for most abelian groups	p. 255
Exercises	p. 263
The symmetric genus	p. 264
Rotation systems and symmetry	p. 265
Reflections	p. 268
Quotient group actions on quotient surfaces	p. 270
Alternative Cayley graphs revisited	p. 271
Group actions and imbeddings	p. 273
Are genus and symmetric genus the same?	p. 275
Euclidean space groups and the torus	p. 276
Triangle groups	p. 279
Exercises	p. 282
Groups of small symmetric genus	p. 283
The Riemann-Hurwitz equation revisited	p. 284
Strong symmetric genus 0	p. 285
Symmetric genus 1	p. 291
The geometry and algebra of groups of symmetric genus 1	p. 295
Hurwitz's theorem	p. 296
Exercises	p. 298
Groups of small genus	p. 300
An example	p. 300
A face-size inequality	p. 302
Statement of main theorem	p. 304
Proof of Theorem 6.4.2: valence d = 4	p. 306
Proof of Theorem 6.4.2: valence d = 3	p. 308
Remarks about Theorem 6.4.2	p. 312
Exercises	p. 317
References	p. 319
Bibliography	p. 333
Supplementary Bibliography	p. 341
Table of Notations	p. 351
Subject Index	p. 357
Table of Contents provided by Syndetics. All Rights Reserved.