A generalization of a theorem of Hoffman

In 1977, Hoffman gave a characterization of graphs with smallest eigenvalue at least -2. In this paper we generalize this result to graphs with smaller smallest eigenvalue. For the proof, we use a combinatorial object named Hoffman graph, introduced by Woo and Neumaier in 1995. Our result says that for every lambda <= -2, if a graph with smallest eigenvalue at least A satisfies some local conditions, then it is highly structured. We apply our result to graphs which are cospectral with the Hamming graph H(3, q), the Johnson graph J(v, 3) and the 2-clique extension of grids, respectively. (C) 2018 Elsevier Inc. All rights reserved.