Business & Economics

Publications » Mathematics » Discrete Mathematics


Price £57.00

temporarily out of stock


A.T. White

ISBN 0444500758
Pages 380

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.

Chapter 1. HISTORICAL SETTING Chapter 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