1 - Introduction

Summary

In Section 1.1 we introduce notation and terminology which will be used throughout the book. In particular, we define line graphs, generalized line graphs and exceptional graphs, all of which have least eigenvalue greater than or equal to —2. Sections 1.2 and 1.3 contain some theorems related to graph spectra which will be used in other chapters. A short history of research on graphs with least eigenvalue —2 is given in Section 1.4.

Basic notions and results

Unless stated otherwise, the graphs we consider are finite undirected graphs without loops or multiple edges, and the eigenvalues we consider are those in the spectrum of a (0, 1)-adjacency matrix (as defined below). A comprehensive introduction to the theory of graph spectra is given in the monograph [CvDSa], along with some of the underlying results from matrix theory. Further results concerning the spectrum of an adjacency matrix can be found in [CvDGT] and [CvRS2]. Here we present only the basic notions which are needed frequently in other chapters. We recommend as a general reference on graph theory the book by Harary [Har]; and as general references on algebraic graph theory the texts by N. L. Biggs [Big] and C. Godsil and G. Royle [GoRo]. Some material related to graphs with least eigenvalue —2 can be found in the books [BrCN] and [CaLi].

If G is a graph with vertices 1, 2, …, n then its adjacency matrix is the n × n matrix A (= A(G)) whose (i, j)-entry a_ij is 1 if the vertices i, j are adjacent (written i ∼ j), and 0 otherwise.