chapter  18
30 Pages

Spectral Graph Theory

Spectral graph theory is the study and exploration of graphs through the eigenvalues and eigenvectors of matrices naturally associated with those graphs. It is intuitively related to attempts to understand graphs through the simulation of processes on graphs and through the consideration of physical systems related to graphs. Spectral graph theory provides many useful algo-

rithms, as well as some that can be rigorously analyzed. We begin this chapter by providing intuition as to why interesting properties of graphs should be revealed by these eigenvalues and eigenvectors. We, then, survey a few applications of spectral graph theory.