×

Spectral generalizations of line graphs. On graphs with least eigenvalue \(-2\). (English) Zbl 1061.05057

London Mathematical Society Lecture Note Series 314. Cambridge: Cambridge University Press (ISBN 0-521-83663-8/pbk). xi, 298 p. (2004).
The scope of this book is broader than its secondary title might suggest. Indeed, from the authors’ preface: “The eigenvalues discussed in this book are those of a \((0,1)\)-adjacency matrix of a finite undirected graph. Line graphs (…) have the property that their least eigenvalue is greater than or equal to \(-2\). This property is shared with generalized line graphs, which can be viewed as line graphs of certain multigraphs. Apart from these classes of examples there are only finitely many further connected graphs with spectrum in the interval \([-2,\infty)\), and these are called exceptional graphs …. Having worked in spectral graph theory for many years, the authors came to see the need for a single source of information on the principal results in this area.”
Chapter 1 contains a lengthy catalog of known results in spectral graph theory, stated with reference(s) but often without proof.
Chapter 2 offers various characterizations of line graphs and generalized line graphs. Let \(H\) be a graph with \(VH=\{v_1,\dots,v_n\}\) and let \(a_1,\dots,a_n\in{N}\). The root multigraph \(\widehat{H}\) is obtained from \(H\) by adjoining \(a_i\) pendant 2-cycles to \(v_i\) \((i=1,\dots,n)\). The generalized line graph \(L(H;a_1,\dots,a_n)\) is the line graph \(L(\widehat{H})\). As the property for a graph to have least eigenvalue greater than or equal to \(-2\) is hereditary, the technique studied in this chapter is that of determining a finite collection of minimal forbidden subgraphs.
Chapter 3 is based on the work of P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult [J. Algebra 43, 305–327 (1976; Zbl 0337.05142)] “using systems of vectors which are called root systems in accordance with the theory of Lie algebras over \(C\).” Here the exceptional graphs are characterized as non-generalized line graphs that are nonetheless representable in the root system \(E_8\) (8-dimensional Euclidean space). The techniques of this chapter are applied to regular graphs in Chapter 4.
Chapter 5 presents star complements, the third and most recent of the three major techniques in this study of graphs with least eigenvalue \(-2\). This approach “enables all of the maximal exceptional graphs to be constructed (Chapter 6).” There are 473 of them, of which 187 are regular, and are described explicitly via seven tables and numerous figures in the 87-page appendix. The largest of these graphs has 36 vertices and maximum valence 28. Chapter 7 is a compendium of results that do not fit neatly into any of the above three approaches.
Included are an extensive bibliography and a helpful index of symbols and terms. This is a deep and challenging piece of work. In addition to more than a basic acquaintance with graph theory, the reader requires as well a substantial background in linear algebra, geometry, and abstract algebra.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
15A18 Eigenvalues, singular values, and eigenvectors
15B36 Matrices of integers

Citations:

Zbl 0337.05142
PDFBibTeX XMLCite