A generalization of a theorem of Hoffman

2016/12/21 by Koolen, Jack H., Yang, Qianqian, Yang, Jae Young
#05C50 #05C62 #05C75 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1612.07085

Abstract

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 λ≤ -2, if a graph with smallest eigenvalue at least λ 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.

Related

• Recent progress on graphs with fixed smallest eigenvalue
• A Bose-Laskar-Hoffman theory for μ-bounded graphs with fixed smallest eigenvalue
• On graphs with smallest eigenvalue at least -3 and their lattices
• A structure theory for regular graphs with fixed smallest eigenvalue
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters