Star complements and exceptional graphs (Q876316)

Let \(G\) be a finite graph of order \(n\) with an eigenvalue \(\mu\) of multiplicity \(k\). (Thus the \(\mu\)-eigenspace of a \((0,1)\)-adjacency matrix of \(G\) has dimension \(k\).) A star complement for \(\mu\) in \(G\) is an induced subgraph \(G-X\) of \(G\) such that \(| X| =k\) and \(G-X\) does not have \(\mu\) as an eigenvalue. An exceptional graph is a connected graph, other than a generalized line graph, whose eigenvalues lie in \([-2,\infty)\). The authors investigate properties of star sets and star complements related to graphs with least eigenvalue \(-2\), and explain some phenomena observed from earlier computer results. Explicitly, they give a simple computer-free proof that each exceptional graph with least eigenvalue greater than \(-2\) is an induced subgraph of an exceptional graph with least eigenvalue equal to \(-2\). They also show how extendability graphs can be used to investigate the regular exceptional graphs. Finally, they establish a property of eigenvectors of exceptional graphs with \(-2\) as a simple eigenvalue.