Handbook of Linear Algebra, 2nd Edition

Chapter 47

Spectral Graph Theory

Steve Butler

Iowa State University

Fan Chung

University of California-San Diego

There are many different ways to associate a matrix with a graph (an introduction of which can be found in Chapter 39 on matrices and graphs). The focus of spectral graph theory is to examine the eigenvalues (or spectrum) of such a matrix and use them to determine structural properties of the graph; or conversely, given a structural property of the graph determine the nature of the eigenvalues of the matrix.

Some of the different matrices we can use for a graph G include the adjacency matrix AG, the (combinatorial) Laplacian matrix LG, the signless Laplacian matrix |LG|, and the normalized Laplacian matrix ℒG. The eigenvalues of these ...