Graphs, Groups and Surfaces (eBook)

Front Cover 1
Graphs, Groups and Surfaces 4
Copyright Page 5
Table of Contents 12
Chapter 1. Historical Setting 16
Chapter 2. A Brief Introduction to Graph Theory 20
2-1. Definition of a graph 20
2-2. Variations of Graphs 21
2-3. Additional Definitions 22
2-4. Operations on Graphs 24
2-5. Problems 27
Chapter 3. The Automorphism Group of a Graph 30
3-1. Definitions 30
3-2. Operations on Permutation Groups 32
3-3. Computing Automorphism Groups of Graphs 33
3-4. Graphs with a Given Automorphism Group 35
3-5. Other Groups of a Graph 35
3-6. Problems 36
Chapter 4. The Cayley Color Graph of a Group Presentation 38
4-1. Definitions 38
4-2. Automorphisms 41
4-3. Properties 47
4-4. Products 47
4-5. Cayley Graphs 50
4-6. Problems 51
Chapter 5. An Introduction to Surface Topology 54
5-1. Definitions 54
5-2. Surfaces and Other 2-manifolds 56
5-3. The Characteristic of a Surface 57
5-4. Two Applications 62
5-5. Pseudosurfaces 68
5-6. Problems 69
Chapter 6. Imbedding Problems in Graph Theory 72
6-1. Answers to Some Imbedding Questions 73
6-2. Definition of "Imbedding" 75
6-3. The Genus of a Graph 76
6-4. The Maximum Genus of a Graph 79
6-5. Genus Formulae for Graphs 82
6-6. Edmonds' Permutation Technique 85
6-7. Imbedding Graphs on Pseudosurfaces 88
6-8. Other Topological Parameters for Graphs 90
6-9. Applications 94
6-10. Problems 96
Chapter 7. The Genus of a Group 98
7.1. Imbeddings of Cayley Color Graphs 98
7.2. Genus Formulae for Groups 103
7.3. Related Results 110
7.4. The Characteristic of a Group 112
7.5. Problems 113
Chapter 8. Map-coloring Problems 116
8.1. Definitions 117
8.2. The Four-color Conjecture 117
8.3. The Five-color Theorem 121
8.4. Other Map-coloring Problems the Heawood Map-coloring Theorem
8.5. A Related Problem 126
8.6. A Four-color Theorem for the Torus 129
8.7. A Nine-color Theorem for the Torus and Klein Bottle 132
8.8. k-degenerate Graphs 133
8.9. Coloring Graphs on Pseudosurfaces 135
8.10. The Cochromatic Number of Surfaces 137
8.11. Problems 138
Chapter 9. Quotient Graphs and Quotient Manifolds 140
9.1. The Genus of Kn 140
9.2. The Theory of Quotient Graphs and Quotient Manifolds. as Applied to Kn 142
9.3. The Genus of Kn (again) 146
9.4. Extending the Theory 151
9.5. The General Theory 157
9.6. Applications to Known Imbeddings 164
9.7. New Applications 167
9.8. Problems 169
Chapter 10. Voltage Graphs 172
10.1. Covering Spaces 172
10.2. Voltage Graphs 175
10.3. Examples 179
10.4. The Heawood Map-coloring Theorem (again) 186
10.5. Strong Tensor Products 188
10.6. Problems 189
Chapter 11. Nonorientable Graph Imbeddings 192
11.1. General Theory 192
11.2. Nonorientable Covering Spaces 195
11.3. Nonorientable Voltage Graph Imbeddings 195
11.4. Examples 197
11.5. The Heawood Map-coloring Theorem, Nonorientable Version 199
11.6. Other Results 200
11.7. Problems 202
Chapter 12. Block Designs 204
12-1. Balanced Incomplete Block Designs 204
12-2. BIBDs and Graph Imbeddings 205
12-3. Examples 206
12-4. Strongly Regular Graphs 207
12-5. Partially Balanced Incomplete Block Designs 209
12-6. PBIBDs and Graph Imbeddings 212
12-7. Examples 213
12-8. Doubling a PBIBD 216
12-9. Problems 218
Chapter 13. Hypergraph Imbeddings 220
13-1. Hypergraphs 220
13-2. Associated Bipartite Graphs 222
13-3. Imbedding Theory for Hypergraphs 222
13-3. Imbedding Theory for Hypergraphs 222
13-4. The Genus of a Hypergraph 226
13-5. The Heawood Map-coloring Theorem, for Hypergraphs 227
13-6. The Genus of a Block Design 228
13-7. An Example 230
13-8. Nonorientable Analogs 232
13-9. Problems 232
Chapter 14. Map Automorphism Groups 234
14-1. Map Automorphisms 234
14-2. Symmetrical Maps 240
14-3. Cayley Maps 244
14-4. Complete Maps 250
14-5. Other Symmetrical Maps 251
14-6. Self-complementary Graphs 252
14-7. Self-dual Maps 254
14-8. Paley Maps 258
14-9. Problems 269
Chapter 15. Change Ringing 272
15-1. Definitions 272
15-2. Notation 275
15-3. General Theory 277
15-4. Four-bell Extents (Minimus) 281
15-5. Five-bell Extents (Doubles) 285
15-6. A New Composition 287
15-7. Problems 291
References 294
Bibliography 318
Index of Symbols 320
Index of Definitions 324