You are here

Spectra of Graphs

Andries E. Brouwer and Willem H. Haemers
Publication Date: 
Number of Pages: 
[Reviewed by
John T. Saccoman
, on

The theory of graph spectra has been getting increasing attention over the last several years. In Graph Theory, the term denotes the eigenvalues of any one of several matrices associated with a graph. These eigenvalues carry much information about a graph’s structure and properties. This text, by Andries Brouwer and Willem Haemers, moves the study further along and provides an outstanding reference for graduate students and researchers interested in the many applications of these eigenvalues and their associated eigenvectors.

Why study graph spectra? Well, the authors give a more mercenary reason in their introduction. “The founders of Google computed the Perron-Frobenius eigenvector of the web graph and became billionaires,” they write. They also mention that this book is the outgrowth of a series of lectures that they gave at Tehran’s Institute for Studies in Theoretical Physics and Mathematics.

After providing some basic definitions of graphs and their associated matrices, their focus is primarily on four matrices associated with graphs: Adjacency, Laplacian (which they refer to as the “Laplace Matrix” throughout the text), the signless Laplacian (ditto), and Seidel. An Introduction to Graph Spectra advances the treatment of the Seidel matrix especially; the 1979 gold standard text by Cvetkovic, Doob and Sachs, Spectra of Graphs, deals mostly with the adjacency matrix, while the more recent An Introduction to Graph Spectra by Cvetkovic, Rowlinson and Simic deals largely with the adjacency matrix and both Laplacian matrices.

As in most of these texts, more linear algebra is assumed than what is generally covered in most non-Electrical Engineering undergraduate courses. In the second chapter alone, Brouwer and Haemers include the Perron-Froebenius Theorem, the Rayleigh Quotient and Gersgorin disks.

Clearly, the authors are well-versed in the literature, providing 358 references and frequently noting where their definitions might differ slightly from those of some previous researchers. The conclusion of each chapter contains some interesting exercises, but no solutions are provided. For this and other reasons mentioned above, the text serves more as a graduate-level monograph than as a resource for anyone but the most advanced undergraduates.

John T. Saccoman is Professor of Mathematics at Seton Hall University in South Orange, NJ.