A structure theory for graphs with fixed smallest eigenvalue

作者：Kim, Hyun Kwang; Koolen, Jack H.^*; Yang, Jae Young

来源：Linear Algebra and Its Applications, 2016, 504: 1-13.

DOI：10.1016/j.laa.2016.03.044

• Smallest eigenvalue
• Structure theory
• Hoffman graph
• Quasi-clique

In this paper, we will give a structure theory for graphs with fixed smallest eigenvalue. In order to do this, the concept of Hoffman graph (as introduced by Woo and Neumaier) is used. Our main result states that for fixed positive integer lambda and any graph G with smallest eigenvalue at least -lambda, there exist dense induced subgraphs Q(1),...

• 出版日期2016-9-1
• 单位中国科学院; 中国科学技术大学