A Survey of Spectral Graph Theory
A survey of spectral graph theory based on topics most relevant to my research. This survey (like most of my website) is in its early stages and does not include any interactive elements yet. Once the topics for the chapters are more established, I will begin adding interactive demos and other elements to make the notebooks more appealing.
This is not an original work, but is based on several surveys of spectral graph theory and a course offered in Matrix Theory at Brigham Young University. The main sources for the definitions and topics are
- Spectra of Graphs by Andries E. Brouwer and Willem H. Haemers
- Spectra of Graphs: Theory and Application by D.M. Cvetković, Doob, and Sachs
- Spectral Graph Theory by Fan Chung
Full bibliographic information is given in each chapter.
A strong background in linear algebra and some knowledge of matrix analysis is assumed.
I. Graph Matrices and Some Spectra
Provides some preliminaries for spectral graph theory, especially characterizations of graph matrices and spectral properties of some families of graphs.
Chapter 2: Spectra of Structured Graphs
Chapter 3: Spectra of Graph Constructions
II. Methods of Proof
Outlines common tools for proofs in spectral graph theory, presenting multiple topics from matrix analysis.
Chapter 4: Equitable Partitions
Chapter 6: Rayleigh Quotients of Graphs
III. Bounds on Graph Spectra
Presents methods for bounding graphs spectra and initial bounds, emphasizing the largest eigenvalue of the adjacency matrix and second-smallest eigenvalue of the Laplacian matrices.
IV. Applications of Graph Spectra
Major results that relate graph spectra directly to invariants of graphs, such as the mixing rate of random walks, expansion, colorings, and isoperimetric constants.