Brouwer A.E., Haemers W.H. Spectra of Graphs

Springer, 2012. — 265 p.Algebraic graph theory is the branch of mathematics that studies graphs by using algebraic properties of associated matrices. In particular, spectral graph theory studies the relation between graph properties and the spectrum of the adjacency matrix or Laplace matrix. And the theory of association schemes and coherent configurations studies the algebra generated by associated matrices. Spectral graph theory is a useful subject. The founders of Google computed the Perron-Frobenius eigenvector of the web graph and became billionaires. The second-largest eigenvalue of a graph gives information about expansion and randomness properties. The smallest eigenvalue gives information about independence number and chromatic number. Interlacing gives information about substructures. The fact that eigenvalue multiplicities must be integral provides strong restrictions. And the spectrum provides a useful invariant.
This book gives the standard elementary material on spectra in Chapter 1_. Important applications of graph spectra involve the largest, second-largest, or smallest eigenvalue, or interlacing, topics that are discussed in Chapters 3 and 4_. Afterwards, special topics such as trees, groups and graphs, Euclidean representations, and strongly regular graphs are discussed. Strongly related to strongly regular graphs are regular two-graphs, and Chapter 10 mainly discusses Seidel’s work on sets of equiangular lines. Strongly regular graphs form the first nontrivial case of (symmetric) association schemes, and Chapter 11 gives a very brief introduction to this topic and Delsarte’s linear programming bound. Chapter 12 very briefly mentions the main facts on distance-regular graphs, including some major developments that have occurred since the monograph [54] was written (proof of the Bannai-Ito conjecture, construction by Van Dam and Koolen of the twisted Grassmann graphs, determination of the connectivity of distance-regular graphs). Instead of working over R, one can work over F_p or Z and obtain more detailed information. Chapter 13 considers p-ranks and Smith normal forms. Finally, Chapters 14 and 15 return to the real spectrum and consider when a graph is determined by its spectrum and when it has only few eigenvalues.
In Spring 2006, both authors gave a series of lectures at IPM, the Institute for Studies in Theoretical Physics and Mathematics, in Tehran. The lecture notes were combined and published as an IPM report. Those notes grew into the present text, of which the on-line version still is called ipm.pdf. We aim at researchers, teachers, and graduate students interested in graph spectra. The reader is assumed to be familiar with basic linear algebra and eigenvalues, but we did include a chapter on some more advanced topics in linear algebra, such as the Perron-Frobenius theorem and eigenvalue interlacing. The exercises at the end of the chapters vary from easy but interesting applications of the treated theory to little excursions into related topics.Graph Spectrum.
Linear Algebra.
Eigenvalues and Eigenvectors of Graphs.
The Second-Largest Eigenvalue.
Trees.
Groups and Graphs.
Topology.
Euclidean Representations.
Strongly Regular Graphs.
Regular Two-graphs.
Association Schemes.
Distance-Regular Graphs.
p-ranks.
Spectral Characterizations.
Graphs with Few Eigenvalues.