×

Spectral graph theory. (English) Zbl 0867.05046

Regional Conference Series in Mathematics. 92. Providence, RI: American Mathematical Society (AMS). xi, 207 p. (1997).
This is a book about a new direction in spectral graph theory (what perhaps should have been pointed out in the title). Instead of the usual Laplacian matrix \(L=T-A\) (\(A\) is the adjacency matrix and \(T\) is the diagonal matrix of vertex degrees) of a graph \(G\), the author introduces the variant \({\mathcal L}= T^{-1/2}LT^{-1/2}\). Eigenvalues of \(\mathcal L\) lie between \(0\) and \(2\) for any graph. The well-known characterization of bipartite graphs by the symmetry of eigenvalues of the adjacency matrix with respect to the zero point is now expressed by the symmetry of eigenvalues of \(\mathcal L\) with respect to point \(1\). No connections and parallels with other directions of the theory of graph spectra is given. The presented theory is mostly developed by the author (about 40 papers are cited) but includes also recent developments on expanders and rapidly mixing Markov chains. The direction seems to be very promissing. Among other things, there is no limitation to the case of regular graphs which is frequently the case with other graph spectra. Motivations for this approach come from differential geometry, in particular by the analogy between Riemannian geometry and spectral graph theory.
Chapter titles: 1. Eigenvalues and Laplacian of a graph, 2. Isoperimetric problems, 3. Diameters and eigenvalues, 4. Paths, flows, and routing, 5. Eigenvalues and quasi-randomness, 6. Expanders and explicit constructions, 7. Eigenvalues of symmetrical graphs, 8. Eigenvalues of subgraphs with boundary conditions, 9. Harnack inequalities, 10. Heat kernels, 11. Sobolev inequalities, 12. Advanced techniques for random walks on graphs. The bibliography contains 251 references.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
58J50 Spectral problems; spectral geometry; scattering theory on manifolds
11F72 Spectral theory; trace formulas (e.g., that of Selberg)
PDFBibTeX XMLCite