"Algebraic Graph Theory" Webpage

Algebraic Graph Theory - Class Notes
From Algebraic Graph Theory Chris Godsil and Gordon Royle, Graduate Texts in Mathematics 207 (Springer, 2001) Godsil and Royle's Algebraic Graph Theory book

Godsil and Royle's Algebraic Graph Theory book

ETSU does not have a formal class on Algebraic Graph Theory. However, we do have a Graph Theory sequence. Notes are online for Graph Theory 1 (MATH 5340) and Graph Theory 2 (MATH 5450). The catalog description for Graph Theory 1 is: "Topics include special classes of graphs, distance in graphs, graphical parameters, connectivity, Eulerian graphs, hamiltonian graphs, networks, and extremal graph theory. Theory and proof techniques will be emphasized." The catalog description for Graph Theory 2 is: "Analyze topics in planar graphs, the Four Color Theorem, vertex/edge colorings, random graphs, and contemporary research topics in graph theory." The authors of Algebraic Graph Theory, Chris Godsil and Gordon Royle, describe algebraic graph theory as "[offering] the pleasure of seeing many unexpected and useful connections between two beautiful, and apparently unrelated, parts of mathematics: algebra and graph theory" (see the page vi).

Godsil and Royle's book is roughly divided into three parts. The first part (Chapters 1 through 7) covers automorphisms and homomorphisms of graphs, with an emphasis on vertex-transitive graphs. The second part (Chapters 8 through 14) covers matrix applications to graphs, including the topics of eigenvalues, interlacing, the Laplacian of a graph, and cuts and flows. The third part (Chapters 15 through 17) covers the connections between graph theory and knot theory, including the topics of the rank polynomial (and its connection with the Jones polynomial of a knot), Reidemeister moves on graphs, and relationships between knots and Eulerian cycles in a graph. A document, The Errata Given by the Authors, is available online. It is brief and only covers errors from Chapters 1 through 10.

Copies of the classnotes are on the internet in PDF format as given below. The notes and supplements may contain hyperlinks to posted webpages; the links appear in red fonts. The "Proofs of Theorems" files were prepared in Beamer. The "Printout of Proofs" are printable PDF files of the Beamer slides without the pauses. These notes have not been classroom tested and may have typographical errors.

Chapter 1. Graphs.
Chapter 2. Groups.
Chapter 3. Transitive Graphs.
Chapter 4. Arc-Transitive Graphs.
Chapter 5. Generalized Polygons and Moore Graphs.
Chapter 6. Homomorphisms.
Chapter 7. Kneser Graphs.
Chapter 8. Matrix Theory.
Chapter 9. Interlacing.
Chapter 10. Strongly Regular Graphs.
Chapter 11. Two-Graphs.
Chapter 12. Line Graphs and Eigenvalues.
Chapter 13. The Laplacian of a Graph.
Chapter 14. Cuts and Flows.
Chapter 15. The Rank Polynomial.
Chapter 16. Knots.
Chapter 17. Knots and Eulerian Cycles.

1.1. Graphs.

1.2. Subgraphs.

1.3. Automorphisms.

Supplement. Proofs of Theorems from Section 1.3. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 1.3.

1.4. Homomorphisms.

Supplement. Proofs of Theorems from Section 1.4. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 1.4.

1.5. Circulant Graphs.

1.6. Johnson Graphs.

Supplement. Proofs of Theorems from Section 1.6. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 1.6.

1.7. Line Graphs.

Supplement. Proofs of Theorems from Section 1.7. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 1.7.

1.8. Planar Graphs.

Study Guide 1. Study Guide for Chapter 1.

2.1. Permutation Groups.

2.2. Counting.

Supplement. Proofs of Theorems from Section 2.2. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.2.

2.3. Asymmetric Graphs. (Contains a proof that almost all graphs are asymmetric in Corollary 2.3.3.)

Supplement. Proofs of Theorems from Section 2.3. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.3.

2.4. Orbits on Pairs.

Supplement. Proofs of Theorems from Section 2.4. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.4.

2.5. Primitivity.

Supplement. Proofs of Theorems from Section 2.5. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.5.

2.6. Primitivity and Connectivity.

Supplement. Proofs of Theorems from Section 2.6. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.6.

Study Guide 2. Study Guide for Chapter 2.

3. Transitive Graphs.

3.1. Vertex-Transitive Graphs.

(This section introduces Cayley graphs.)

Supplement. Proofs of Theorems from Section 3.1. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 3.1.

Supplement. Cayley Graphs: Abstract Definitions and Concrete Pictures (in PowerPoint).

Supplement. Every Finite Group is the Automorphism Group of Some Graph - Frucht's Theorem.

Supplement. Proofs of Theorems from Frucht's Theorem Supplement. (prepared in Beamer).
Supplement. Printouts of Proofs from Frucht's Theorem Supplement.

3.2. Edge-Transitive Graphs.

Supplement. Proofs of Theorems from Section 3.2. (prepared in Beamer; incomplete).
Supplement. Printouts of Proofs from Section 3.2. (incomplete)

3.3. Edge Connectivity.

3.4. Vertex Connectivity.

3.5. Matchings.

3.6. Hamilton Paths and Cycles.

3.7. Cayley Graphs.

Supplement. Proofs of Theorems from Section 3.7. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 3.7.

3.8. Directed Cayley Graphs with No Hamilton Cycle.

Supplement. Proofs of Theorems from Section 3.8. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 3.8.

3.9. Retracts.

3.10. Transpositions.

Supplement. Proofs of Theorems from Section 3.10. (prepared in Beamer).
Supplement. Printouts of Proofs from Section 3.10.

Study Guide 3. Study Guide for Chapter 3.

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.

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.

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.

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. The Cartesian Product.

7.15. Strong Products and Colourings.

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.

9. Interlacing.

9.1. Interlacing.

9.2. Inside and Outside 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.

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.

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.

12. Line Graphs and Eigenvalues.

12.1. Generalized Line Graphs.

12.2. Star-Crossed 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 Graphs.

13. The Laplacian of a Graphs.

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

13.8. How to Draw a Graph.

13.9. The Generalized Laplacian.

13.10. Multiplicities.

13.11. Embeddings.

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.

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.

16.1. Knots and Their Projections.

16.2. Reidemeister Moves.

16.3. Signed Plane Graphs.

16.4. Reidemeister Moves on Graphs.

16.5. Redemeister Invariants.

16.6. The Kauffman Bracket.

16.7. The Jones Polynomial.

16.8. Connectivity.

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.

Return to Bob Gardner's home page