You are here

An Introduction to the Theory of Graph Spectra

Cambridge University Press
Number of Pages: 

The word “spectrum” means different things in different areas of mathematics. For those of us in Graph Theory, the word 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.

In 1979, Cvetković, Doob and Sachs co-wrote Spectra of Graphs, a book of great importance in Algebraic Graph Theory. The book is valued for its theoretical content as well as the Appendices, which include drawings, characteristic polynomials, and adjacency matrix eigenvalues for a wide range of non-isomorphic graphs containing a particular number of nodes and edges. This work furthered Biggs’ excellent Algebraic Graph Theory. Cvetković, with two new collaborators, Rowlinson and Simić, have produced a worthy companion to the other two texts.

In this latest text, Cvetković, Rowlinson and Simić present modern advances in the field, including chapters on graph operations and modifications as well as Laplacian matrices not included in most other texts. They also update the applications of spectral techniques to other sciences. The book follows two others that they have written on more specific Graph Spectra topics, also for Cambridge University Press — Eigenspaces of Graphs and Spectral Generalizations of Line Graphs — but this is an excellent survey to read before delving into those two. The appendices include spectra and characteristic polynomials for various matrices of many different graphs, and the text includes a very large number of references.

An Introduction to Graph Spectra is an excellent resource for researchers in the field as well as graduate students and (very) advanced undergraduates. Their claim that readers need know “a little” Graph Theory and “a little” Linear Algebra is a bit of a stretch; a decent background in Linear Algebra or Matrix Theory would help the reader appreciate the material even more.

I have to mention one slight omission from the text. On page 193, Chapter 7, the authors, reference a paper by Kelmans and Hammer, “Laplacian spectra and spanning trees of threshold graphs,” that appeared in Discrete Applied Mathematics 65 (1996). pp. 255–273. The formula presented there does not work in all cases; it was corrected in “A correction in the formula for the number of spanning trees in threshold graphs” by S. Bleiler et. al., appearing in the Australasian Journal of Combinatorics, 37 (2007), pp. 205–213.

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

Date Received: 
Monday, November 23, 2009
Include In BLL Rating: 
D. Cvetković, P. Rowlinson, and S. Simić
London Mathematical Society Student Texts 75
Publication Date: 
John T. Saccoman
BLL Rating: 

Preface; 1. Introduction; 2. Graph operations and modifications; 3. Spectrum and structure; 4. Characterizations by spectra; 5. Structure and one eigenvalue; 6. Spectral techniques; 7. Laplacians; 8. Additional topics; 9. Applications; Appendix; Bibliography; Index of symbols; Index.

Publish Book: 
Modify Date: 
Wednesday, June 8, 2011