Algebraic Graph Theory

Preface 1 Graphs 1.1 Graphs 1.2 Subgraphs 1.3 Automorphisms 1.4 Homomorphisms 1.5 Circulant Graphs 1.6 Johnson Graphs 1.7 Line Graphs 1.8 Planar Graphs Exercises Notes References 2 Groups 2.1 Permutation Groups 2.2 Counting 2.3 Asymmetric Graphs 2.4 Orbits on Pairs 2.5 Primitivity 2.6 Primitivity and Connectivity Exercises Notes References 3 Transitive Graphs 3.1 Vertex-Transitive Graphs 3.2 Edge-Transitive Graphs 3.3 Edge Connectivity 3.4 Vertex Connectivity 3.5 Matchings 3.6 Hamilton Paths and Cycles 3.7 Cayley Graphs 3.8 Directed Cayley Graphs with No Hamilton Cycles 3.9 Retracts 3.10 Transpositions Exercises Notes References 4 Arc-Transitive Graphs 4.1 Arc-Transitive Graphs 4.2 Arc Graphs 4.3 Cubic Arc-Transitive Graphs 4.4 The Petersen Graph 4.5 Distance-Transitive Graphs 4.6 The Coxeter Graph 4.7 Tutte's 8-Cage Exercises Notes References 5 Generalized Polygons and Moore Graphs 5.1 Incidence Graphs 5.2 Projective Planes 5.3 A Family of Projective Planes 5.4 Generalized Quadrangles 5.5 A Family of Generalized Quadrangles 5.6 Generalized Polygons 5.7 Two Generalized Hexagons 5.8 Moore Graphs 5.9 The Hoffman-Singleton Graph 5.10 Designs Exercises Notes References 6 Homomorphisms 6.1 The Basics 6.2 Cores 6.3 Products …… 7 Kneser Graphs 8 Matrix Theory 9 Interlacing 10 Strongly Regular Graphs 11 Two-Graphs 12 Line Graphs and Eigenvalues 13 The Laplacian of a Graph 14 Cuts and Flows 15 The Rank Polynomial 16 Knots 17 Knots and Eulerian Cycles Glossary of Symbols Index