A Brief Introduction to Spectral Graph Theory

There are many undergraduate books on graph theory in general, but few of those books highlight the connection of graph theory with other mathematical fields, for example with group theory or linear algebra.

The book under review attempts one such approach, emphasizing the link with linear algebra via the adjacency and Laplacian matrices associated to a given graph. Both such matrices are real symmetric and thus have exactly n real eigenvalues, where n is the number of vertices of the graph.

The key point of spectral graph theory is to obtain information on the graph from information on the eigenvalues of its adjacency or Laplacian matrix. After a few examples of computations of the eigenvalues of the adjacency matrix of some concrete graphs, the author introduces general methods to compute these eigenvalues for families of graphs, and proves some general results on the spectra of graphs. The author illustrates the power of the spectral approach obtaining some structural properties of a given graph or a family of graphs from properties of the corresponding eigenvalues.

The book is well written, assuming little background either in graph theory or in algebra. To use it as a text for a topics course for senior undergraduates, the instructor would have to provide the exercises since there are very few in the text.

Felipe Zaldivar is Professor of Mathematics at the Universidad Autonoma Metropolitana-I, in Mexico City. His e-mail address is fz@xanum.uam.mx.