You are here

Inequalities for Graph Eigenvalues

Zoran Stanić
Cambridge University Press
Publication Date: 
Number of Pages: 
London Mathematical Society Lecture Notes Series 423
[Reviewed by
John D. Cook
, on

Hearing about eigenvalues of a graph may be puzzling at first. What does it even mean for a graph to have eigenvalues? We usually think of a graph as a static object, not something that maps things to other things. How could a graph map something to a multiple of itself?

Strictly speaking, graphs don’t have eigenvalues; matrices associated with graphs have eigenvalues. We call these eigenvalues of the graph. We can learn properties of a graph from the eigenvalues of these matrices, and vice versa.

There are several matrices associated with graphs. Zoran Stanić’s book Inequalities for Graph Eigenvalues primarily considers three such matrices: the adjacency matrix, the Laplacian, and the signless Laplacian. The most basic of these is the adjacency matrix A. The (i, j) element of A is 1 if there is an edge between the ith and jth vertex and zero otherwise. Stanić only considers undirected graphs and so we only care whether an edge exists, not its orientation, and so the adjacency matrix is symmetric, which simplifies the study of its spectral theory.

Define D to be the diagonal matrix whose (i, i) entry is the degree of the ith vertex, i.e. the number of edges attached to that vertex. Then the Laplacian matrix of the graph is L = DA and the signless Laplacian matrix is Q = D + A.

Inequalities for Graph Eigenvalues primarily studies the eigenvalues of A, L, and Q. (The book briefly considers a few more variations on the Laplacian matrix.) These three matrices are closely related. Several theorems hold for A, L, and Q, in which case the author uses M to denote any one of these three matrices. The book also gives several theorems showing how the eigenvalues of each matrix relate to those of the other matrices.

Inequalities for Graph Eigenvalues starts with a brisk review of graph theory and spectral theory. One could read the book without prior exposure to either of these topics, but the first few pages would be slow reading.

As the title indicates, the emphasis of the book is on inequalities for eigenvalues. Most often a theorem will give an upper or lower bound on a particular eigenvalue in terms of properties of a graph. Of course such theorems could also be read as bounding some property of a graph in terms of an eigenvalue, but typically the eigenvalue is alone on one side of the inequality and a more complicated expression involving graph properties is on the other side. One nice feature of the book, and one that could easily be overlooked, is an index of inequalities in the back which lists the most important variables in each inequality. It would be good to see more books include something like this.

In addition to eigenvalue inequalities, Stanić considers extremal graphs associated with many of these inequalities, particular graphs that obtain (or nearly obtain) the bound indicated by the inequality.

Inequalities for Graph Eigenvalues is primarily theoretical. There is little space devoted to applications or to algorithms. The inequalities most directly use information about a graph to infer properties of matrix eigenvalues rather than the other way around. However, a better understanding of the spectra of associated matrices leads to a better understanding of graphs.

John D. Cook is an independent consultant and blogs regularly at The Endeavour.

1. Introduction
2. Spectral radius
3. Least eigenvalue
4. Second largest eigenvalue
5. Other eigenvalues of the adjacency matrix
6. Laplacian eigenvalues
7. Signless Laplacian eigenvalues
8. Inequalities for multiple eigenvalues
9. Other spectra of graphs
Subject index.