Book:Chris Godsil/Algebraic Graph Theory

Chris Godsil and Gordon Royle: Algebraic Graph Theory

Published $\text {2001}$, Springer

ISBN 0-387-95220-9

Subject Matter

• Graph Theory

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.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

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.8 Erdös-Ko-Rado

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.8 Generalized Quadrangles

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