Preface
Chapter 1. Eigenvalues and the Laplacian of a graph
1.1. Introduction
1.2. The Laplacian and eigenvalues
1.3. Basic facts about the spectrum of a graph
1.4. Eigenvalues of weighted graphs
1.5. Eigenvalues and random walks
Chapter 2. Isoperimetric problems
2.1. History
2.2. The Cheeger constant of a graph
2.3. The edge expansion of a graph
2.4. The vertex expansion of a graph
2.5. A characterization of the Cheeger constant
2.6. Isoperimetric inequalities for cartesian products
Chapter 3. Diameters and eigenvalues
3.1. The diameter of a graph
3.2. Eigenvalues and distances between two subsets
3.3. Eigenvalues and distances among many subsets
3.4. Eigenvalue upper bounds for manifolds
Chapter 4. Paths, flows, and routing
4.1. Paths and sets of paths
4.2. Flows and Cheeger constants
4.3. Eigenvalues and routes with small congestion
4.4. Routing in graphs
4.5. Comparison theorems
Chapter 5. Eigenvalues and quasi-randomness
5.1. Quasi-randomness
5.2. The discrepancy property
5.3. The deviation of a graph
5.4. Quasi-random graphs
Chapter 6. Expanders and explicit constructions
6.1. Probabilistic methods versus explicit constructions
6.2. The expanders
6.3. Examples of explicit constructions
6.4. Applications of expanders in communication networks
6.5. Constructions of graphs with small diameter and girth
6.6. Weighted Laplacians and the Lovasz v function
Chapter 7. Eigenvalues of symmetrical graphs
7.1. Symmetrical graphs
7.2. Cheeger constants of symmetrical graphs
7.3. Eigenvalues of symmetrical graphs
7.4. Distance transitive graphs
7.5. Eigenvalues and group representation theory
7.6. The vibrational spectrum of a graph
Chapter 8. Eigenvalues of subgraphs with boundary conditions
8.1. Neumann eigenvalues and Dirichlet eigenvalues
8.2. The Neumann eigenvatues of a subgraph
8.3. Neumann eigenvalues and random walks
8.4. Dirichlet eigenvalues
8.5. A matrix-tree theorem and Dirichlet eigenvalues
