# Graphs of Groups on Surfaces

**Interactions and Models**

**By**

- A.T. White, Western Michigan University, Kalamazoo, MI 49008, USA

The book, suitable as both an introductory reference and as a text book in the rapidly growing field of topological graph theory, models both maps (as in map-coloring problems) and groups by means of graph imbeddings on sufaces. Automorphism groups of both graphs and maps are studied. In addition connections are made to other areas of mathematics, such as hypergraphs, block designs, finite geometries, and finite fields. There are chapters on the emerging subfields of enumerative topological graph theory and random topological graph theory, as well as a chapter on the composition of English church-bell music. The latter is facilitated by imbedding the right graph of the right group on an appropriate surface, with suitable symmetries. Throughout the emphasis is on Cayley maps: imbeddings of Cayley graphs for finite groups as (possibly branched) covering projections of surface imbeddings of loop graphs with one vertex. This is not as restrictive as it might sound; many developments in topological graph theory involve such imbeddings.

The approach aims to make all this interconnected material readily accessible to a beginning graduate (or an advanced undergraduate) student, while at the same time providing the research mathematician with a useful reference book in topological graph theory. The focus will be on beautiful connections, both elementary and deep, within mathematics that can best be described by the intuitively pleasing device of imbedding graphs of groups on surfaces.

### Book information

- Published: April 2001
- Imprint: NORTH-HOLLAND
- ISBN: 978-0-444-50075-5

### Reviews

...this is a very well-written and readable book, which I recommend on anyone wanting to learn this particular approach to the subject.

Bulletin of the London Mathematical Society

### Table of Contents

Chapter 1. HISTORICAL SETTINGChapter 2. A BRIEF INTRODUCTION TO GRAPH THEORY

2-1. Definition of a Graph

2-2. Variations of Graphs

2-3. Additional Definitions

2-4. Operations on Graphs

2-5. Problems

Chapter 3. THE AUTOMORPHISM GROUP OF A GRAPH

3-1. Definitions

3-2. Operations on Permutations Groups

3-3. Computing Automorphism Groups of Graphs

3-4. Graphs with a Given Automorphism Group

3-5. Problems

Chapter 4. THE CAYLEY COLOR GRAPH OF A GROUP PRESENTATION

4-1. Definitions

4-2. Automorphisms

4-3. Properties

4-4. Products

4-5. Cayley Graphs

4-6. Problems

Chapter 5. AN INTRODUCTION TO SURFACE TOPOLOGY

5-1. Definitions

5-2. Surfaces and Other 2-manifolds

5-3. The Characteristic of a Surface

5-4. Three Applications

5-5. Pseudosurfaces

5-6. Problems

Chapter 6. IMBEDDING PROBLEMS IN GRAPH THEORY

6-1. Answers to Some Imbedding Questions

6-2. Definition of "Imbedding"

6-3. The Genus of a Graph

6-4. The Maximum Genus of a Graph

6-5. Genus Formulae for Graphs

6-6. Rotation Schemes

6-7. Imbedding Graphs on Pseudosurfaces

6-8. Other Topological Parameters for Graphs

6-9. Applications

6-10. Problems

Chapter 7. THE GENUS OF A GROUP

7-1. Imbeddings of Cayley Color graphs

7-2. Genus Formulae for Groups

7-3. Related Results

7-4. The Characteristic of a Group

7-5. Problems

Chapter 8. MAP-COLORING PROBLEMS

8-1. Definitions and the Six-Color Theorem

8-2. The Five-Color Theorem

8-3. The Four-Color Theorem

8-4. Other Map-Coloring Problems: The Heawood Map-Coloring Theorem

8-5. A Related Problem

8-6. A Four-Color Theorem for the Torus

8-7. A Nine-Color Theorem for the Torus and Klein Bottle

8-8. k-degenerate Graphs

8-9. Coloring Graphs on Pseudosurfaces

8-10. The Cochromatic Number of Surfaces

8-11. Problems

Chapter 9. QUOTIENT GRAPHS AND QUOTIENT MANIFOLDS:CURRENT GRAPHS AND THE COMPLETE GRAPH THEOREM

9-1. The Genus of Kn

9-2. The Theory of Current Graphs as Applied to Kn

9-3. A Hint of Things to Come

9-4. Problems

Chapter 10. VOLTAGE GRAPHS

10-1. Covering Spaces

10-2. Voltage Graphs

10-3. Examples

10-4. The Heawood Map-coloring Theorem (again)

10-5. Strong Tensor Products

10-6. Covering Graphs and Graphical Products

10-7. Problems

Chapter 11. NONORIENTABLE GRAPH IMBEDDINGS

11-1. General Theory

11-2. Nonorientable Covering Spaces

11-3. Nonorientable Voltage Graph Imbeddings

11-4. Examples

11-5. The Heawood Map-coloring Theorem, Nonorientable Version

11-6. Other Results

11-7. Problems

Chapter 12. BLOCK DESIGNS

12-1. Balanced Incomplete Block Designs

12-2. BIBDs and Graph Imbeddings

12-3. Examples

12-4. Strongly Regular Graphs

12-5. Partially Balanced Incomplete Block Designs

12-6. PBIBDs and Graph Imbeddings

12-7. Examples

12-8. Doubling a PBIBD

12-9. Problems

Chapter 13. HYPERGRAPH IMBEDDINGS

13-1. Hypergraphs

13-2. Associated Bipartite Graphs

13-3. Imbedding Theory for Hypergraphs

13-4. The Genus of a Hypergraph

13-5. The Heawood Map-Coloring Theorem, for Hypergraphs

13-6. The Genus of a Block Design

13-7. An Example

13-8. Nonorientable Analogs

13-9. Problems

Chapter 14. FINITE FIELDS ON SURFACES

14-1. Graphs Modelling Finite Rings

14-2. Basic Theorems About Finite Fields

14-3. The Genus of Fp

14-4. The Genus of Fpr

14-5. Further Results

14-6. Problems

Chapter 15. FINITE GEOMETRIES ON SURFACES

15-1. Axiom Systems for Geometries

15-2. n-Point Geometry

15-3. The Geometries of Fano, Pappus, and Desargues

15-4. Block Designs as Models for Geometries

15-5. Surface Models for Geometries

15-6. Fano, Pappus, and Desargues Revisited

15-7. 3-Configurations

15-8. Finite Projective Planes

15-9. Finite Affine Planes

15-10. Ten Models for AG(2,3)

15-11. Completing the Euclidean Plane

15-12. Problems

Chapter 16. MAP AUTOMORPHISM GROUPS

16-1. Map Automorphisms

16-2. Symmetrical Maps

16-3. Cayley Maps

16-4. Complete Maps

16-5. Other Symmetrical Maps

16-6. Self -Complementary Graphs

16-7. Self-dual Maps

16-8. Paley Maps

16-9. Problems

Chapter 17. ENUMERATING GRAPH IMBEDDINGS

17-1. Counting Labelled Orientable 2-Cell Imbeddings

17-2. Counting Unlabelled Orientable 2-Cell Imbeddings

17-3. The Average Number of Symmetries

17-4. Problems

Chapter 18. RANDOM TOPOLOGICAL GRAPH THEORY

18-1. Model I

18-2. Model II

18-3. Model III

18-4. Model IV

18-5. Model V

18-6. Model VI- Random Cayley Maps

18-7. Problems

Chapter 19. CHANGE RINGING

19-1. The Setting

19-2. A Mathematical Model

19-3. Minimus

19-4. Doubles

19-5. Minor

19-6. Triples and Fabian Stedman

19-7. Extents on n Bells

19-8. Summary

19-9. Problems

REFERENCES. BIBLIOGRAPHY. INDEX OF SYMBOLS. INDEX OF DEFINITIONS