Graphs with least eigenvalue \(-2\): The star complement technique (Q5949011)

If a connected graph has \(-2\) as its least eigenvalue, then it is either a generalized line graph or a graph representable in the root system \(E_8\) (which is proved in \textit{R. I. Cameron} et al. [J. Algebra 43, 305-327 (1976; Zbl 0337.05142)]). The connected graphs which have least eigenvalue greater than or equal to \(-2\), and which are not generalized line graphs, are called exceptional. Search for exceptional graphs lasted for some 30 years and nowadays it is known that there are 573 of them. Some further details on exceptional graphs can be found in \textit{F. C. Bussemaker} and \textit{A. Neumaier} [Math. Comput. 59, 583-608 (1992; Zbl 0770.05060)]. Let \(G\) be a simple graph with eigenvalue \(\mu\) of its adjacency matrix. If \(\mu\) has multiplicity \(k\) then a star set for \(\mu\) is a set \(X\) of \(k\) vertices of \(G\) such that \(\mu\) is not an eigenvalue of \(G-X\). Here \(G-X\) is the subgraph of \(G\) induced by \(V(G)\setminus X\), and it is called the star complement for \(\mu\). The main result of this paper is that a graph is exceptional if and only if it has an exceptional star complement for \(-2\). This result is then used to show that it is possible to find exceptional graphs using star complements for \(-2\), without any recourse to root systems. The authors also show that certain graphs with least eigenvalue \(-2\) can be characterized by star complements for \(-2\).