Some Topics in Graph Theory

✍ Scribed by Hian Poh Yap

• Publisher: Cambridge University Press
• Year: 1986
• Tongue: English
• Leaves: 238
• Series: London Mathematical Society Lecture Note Series
• Category: Library

✦ Synopsis

This book provides a rapid introduction to topics in graph theory typically covered in a graduate course. The author sets out the main recent results in several areas of current research in graph theory. Topics covered include edge-colourings, symmetries of graphs, packing of graphs, and computational complexity. Professor Yap is able to lead the reader to the forefront of research and to describe some of the open problems in the field. The choice of material presented has arisen from courses given at the National University of Singapore and each chapter contains numerous examples and exercises for the reader.

✦ Table of Contents

Contents......Page 7
Introduction......Page 5
1. Basic graph-theoretic terms......Page 9
2. Groups acting on sets......Page 12
1. Introduction and definitions......Page 17
2. A generalization of Vizing's theorem......Page 22
3. Critical graphs......Page 29
4. Constructions for critical graphs......Page 34
5. Bounds on the size of critical graphs......Page 45
6. Critical graphs of small order......Page 51
7. Planar graphs......Page 57
8. 1-factorization of regular graphs of high degree......Page 60
9. Applications to vertex-colourings......Page 64
10. Applications to the reconstruction of latin squares......Page 76
11. Concluding remarks......Page 84
References......Page 89
1. The automorphism group of a graph......Page 96
2. Asymmetric graphs......Page 100
3. Graphs with a given group......Page 104
4. Vertex-transitive graphs......Page 107
5. Vertex-transitive graphs of prime order......Page 115
6. Auto-extensions......Page 119
7. s-transitive cubic graphs......Page 123
8. 4-ultratransitive graphs......Page 131
9. Hamilton cycles in Cayley graphs......Page 141
10. Concluding remarks......Page 149
References......Page 153
1. Introduction and definitions......Page 164
2. Packing n - 1 trees of different size into Kn......Page 165
3. Packing two graphs of small size......Page 171
4. Packing two graphs of order n having total size at most 2n - 3......Page 173
5. Packing a tree of order n with an (n, n-1) graph......Page 178
6. Packing a tree of order n with an (n,n) graph......Page 183
7. Packing two (n,n-1) graphs......Page 188
8. Packing two graphs of order n having total size at most 2n - 2......Page 196
References......Page 202
1. Introduction and definitions......Page 204
2. Some elusive properties; the simple strategy to......Page 208
3. Some non-elusive properties......Page 213
4. The diagram of a non-elusive property......Page 217
5. The odd-even balanced condition......Page 221
6. The Aanderaa-Rosenberg Conjecture......Page 226
7. A counterexample to the Rivest-Vuillemin Conjecture......Page 228
8. A lower bound for the computational complexity of graph properties......Page 231
References......Page 234
Index of subjects......Page 236
Index of notation......Page 238