Graphs with Least Eigenvalue - 2: The Star Complement Technique

Abstract

Let G be a connected graph with least eigenvalue -2, of multiplicity k. A star complement for -2 in G is an induced subgraph H = G - X such that |X| = k and -2 is not an eigenvalue of H. In the case that G is a generalized line graph, a characterization of such subgraphs is used to decribe the eigenspace of -2. In some instances, G itself can be characterized by a star complement. If G is not a generalized line graph, G is an exceptional graph, and in this case it is shown how a star complement can be used to construct G without recourse to root systems.