A recursive construction of the regular exceptional graphs with least eigenvalue –2

Abstract

In spectral graph theory a graph with least eigenvalue $-2$ is exceptional if it is connected, has least eigenvalue greater than or equal to $-2$, and it is not a generalized line graph. A $(\kappa ,\tau )$-regular set $S$ of a graph is a vertex subset, inducing a $\kappa$-regular subgraph such that every vertex not in $S$ has $\tau$ neighbors in $S$. We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets.