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 (κ τ)-regular set S of a graph is a vertex subset, inducing a κ-regular subgraph such that every vertex not in S has t neighbors in S. We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets.