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 τ neighbors in S. We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets.
展开▼
