Preface

Summary

The eigenvalues discussed in this book are those of a (0, 1)-adjacency matrix of a finite undirected graph. Line graphs, familiar to graph-theorists for decades, 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, ∞), and these are called exceptional graphs. This book deals with line graphs, generalized line graphs and exceptional graphs, in the context of spectral properties of 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. Work began early in 2000, and the principal motivation for writing the book at this juncture was the construction of the maximal exceptional graphs in 1999. The working title has become the subtitle on the grounds that ‘Graphs with least eigenvalue -2’ might appear unreasonably specialized to the casual observer. In fact, the subtitle is not wholly accurate in that it is necessary to treat also the graphs with least eigenvalue greater than —2.

The requirement that the spectrum of a graph lies in [—2, ∞) is a natural one, and in principle not a restriction at all. The reason is to be found in the classical result of H. Whitney, who showed in 1932 that two connected graphs (with more than three vertices) are isomorphic if and only if their line graphs are isomorphic.