5 - Star complements

Summary

Let G be a graph of order n with μ as an eigenvalue of multiplicity k. In Section 5.1, we define a star complement for μ in terms of the orthogonal projection of IRⁿ onto the eigenspace ε(μ). We show that the star complements for μ in G are just the induced subgraphs of G of order n– k that do not have μ as an eigenvalue, and we derive the properties of star complements required in this book. (For a survey of star complements, see [Row5].) In Section 5.2 we introduce the notion of a foundation for the root multigraph of a generalized line graph: it is used to characterize star complements for —2 in generalized line graphs, and at the same time to describe the eigenspace of —2. In Section 5.3, we show that a graph is exceptional if and only if it has an exceptional star complement for-2. By interlacing, such a star complement has least eigenvalue greater than —2 and hence is one of 573 known graphs (see Table A2 and Theorem 2.3.20). It follows that the exceptional graphs can be constructed, as extensions of star complements, without recourse to root systems. In Section 5.4 we show how certain graphs with least eigenvalue —2 can be characterized by star complements for-2. Finally, in Section 5.5 we discuss the role of switching in the construction of exceptional graphs from star complements.

Basic properties

Let G be a graph with vertex set V(G) = {1, …, n} and adjacency matrix A. Let {e₁, …, e_n} be the standard orthonormal basis of IRⁿ and P be the matrix which represents the orthogonal projection of IRⁿ onto the eigenspace ε(μ) of A with respect to {e₁, …, e_n}.