# Book:Chris Godsil/Algebraic Graph Theory

## Chris Godsil and Gordon Royle: Algebraic Graph Theory

Published $\text {2001}$, Springer

ISBN 0-387-95220-9

### Contents

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.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
6.4 The Map Graph
6.5 Counting Homomorphisms
6.6 Products and Colourings
6.7 Uniquely Colourable Graphs
6.8 Foldings and Covers
6.9 Cores with No Triangles
6.10 The Andrásfai Graphs
6.11 Colouring Andrásfai Graphs
6.12 A Characterization
6.13 Cores of Vertex-Transitive Graphs
6.14 Cores of Cubic Vertex-Transitive Graphs
Exercises
Notes
References
7 Kneser Graphs
7.1 Fractional Colourings and Cliques
7.2 Fractional Cliques
7.3 Fractional Chromatic Number
7.4 Homomorphisms and Fractional Colourings
7.5 Duality
7.6 Imperfect Graphs
7.7 Cyclic Interval Graphs
7.9 Homomorphisms of Kneser Graphs
7.10 Induced Homomorphisms
7.11 The Chromatic Number of the Kneser Graph
7.12 Gale's Theorem
7.13 Welzl's Theorem
7.14 Strong Products and Colourings
Exercises
Notes
References
8 Matrix Theory
8.1 The Adjacency Matrix
8.2 The Incidence Matrix
8.3 The Incidence Matrix of an Oriented Graph
8.4 Symmetric Matrices
8.5 Eigenvectors
8.6 Positive Semidefinite Matrices
8.7 Subharmonic Functions
8.8 The Perron-Frobenius Theorem
8.9 The Rank of a Symmetric Matrix
8.10 The Binary Rank of the Adjacency Matrix
8.11 The Symplectic Graphs
8.12 Spectral Decomposition
8.13 Rational Functions
Exercises
Notes
References
9 Interlacing
9.1 Interlacing
9.2 Inside and Outside the Petersen Graph
9.3 Equitable Partitions
9.4 Eigenvalues of Kneser Graphs
9.5 More Interlacing
9.6 More Applications
9.7 Bipartite Subgraphs
9.8 Fullerenes
9.9 Stability of Fullerenes
Exercises
Notes
References
10 Strongly Regular Graphs
10.1 Parameters
10.2 Eigenvalues
10.3 Some Characterizations
10.4 Latin Square Graphs
10.5 Small Strongly Regular Graphs
10.6 Local Eigenvalues
10.7 The Krein Bounds
10.9 Lines of Size Three
10.10 Quasi-Symmetric Designs
10.11 The Witt Design on 23 Points
10.12 The Symplectic Graphs
Exercises
Notes
References
11 Two-Graphs
11.1 Equiangular Lines
11.2 The Absolute Bound
11.3 Tightness
11.4 The Relative Bound
11.5 Switching
11.6 Regular Two-Graphs
11.7 Switching and Strongly Regular Graphs
11.8 The Two-Graph on 276 Vertices
Exercises
Notes
References
12 Line Graphs and Eigenvalues
12.1 Generalized Line Graphs
12.2 Star-Closed Sets of Lines
12.3 Reflections
12.4 Indecomposable Star-Closed Sets
12.5 A Generating Set
12.6 The Classification
12.7 Root Systems
12.8 Consequences
12.9 A Strongly Regular Graph
Exercises
Notes
References
13 The Laplacian of a Graph
13.1 The Laplacian Matrix
13.2 Trees
13.3 Representations
13.4 Energy and Eigenvalues
13.5 Connectivity
13.6 Interlacing
13.7 Conductance and Objects
13.8 How to Draw a Graph
13.9 The Generalized Laplacian
13.10 Multiplicities
13.11 Embeddings
Exercises
Notes
References
14 Cuts and Flows
14.1 The Cut Space
14.2 The Flow Space
14.3 Planar Graphs
14.4 Bases and Ear Decompositions
14.5 Lattices
14.6 Duality
14.7 Integer Cuts and Flows
14.8 Projections and Duals
14.9 Chip Firing
14.10 Two Bounds
14.11 Recurrent States
14.12 Critical States
14.13 The Critical Group
14.14 Voronoi Polyhedra
14.15 Bicycles
14.16 The Principal Tripartition
Exercises
Notes
References
15 The Rank Polynomial
15.1 Rank Functions
15.2 Matroids
15.3 Duality
15.4 Restriction and Contraction
15.5 Codes
15.6 The Deletion-Contraction Algorithm
15.7 Bicycles in Binary Codes
15.8 Two Graph Polynomials
15.9 Rank Polynomial
15.10 Evaluations of the Rank Polynomial
15.11 The Weight Enumerator of a Code
15.12 Colourings and Codes
15.13 Signed Matroids
15.14 Rotors
15.15 Submodular Functions
Exercises
Notes
References
16 Knots
16.1 Knots and Their Projections
16.2 Reidemeister Moves
16.3 Signed Plane Graphs
16.4 Reidemeister Moves on Graphs
16.5 Reidemeister Invariants
16.6 The Kauffman Bracket
16.7 The Jones Polynomial
16.8 Connectivity
Exercises
Notes
References
17 Knots and Eulerian Cycles
17.1 Eulerian Partitions and Tours
17.2 The Medial Graph
17.3 Link Components and Bicycles
17.4 Gauss Codes
17.5 Chords and Circles
17.6 Flipping Words
17.7 Characterizing Gauss Codes
17.8 Bent Tours and Spanning Trees
17.9 Bent Partitions and the Rank Polynomial
17.10 Maps
17.11 Orientable Maps
17.12 Seifert Circles
17.13 Seifert Circles and Rank
Exercises
Notes
References
Glossary of Symbols
Index