Graphs with Large Clique Number whose Second Largest Eigenvalue does not Exceed $(\sqrt{5}-1)/2$

Abstract

In 1993, Cao and Hong [J. Graph Theory, 17 (1993), 325-331] posed the problem of characterizing graphs whose second largest eigenvalue is less than the golden section bound. In further considerations, the problem is extended to `less than or equal to the golden section'. Several results giving partial characterizations appeared in the proceeding years, and what have remained are the most complicated cases. These cases are treated very sporadically in the period of the next 25 years. In this paper, we give a positive resolution to the problem for graphs containing a large clique. Actually, we characterize graphs whose second largest eigenvalue does not exceed the golden section bound and whose clique number is at least 54. If a graph has a pendant vertex, the result is improved to clique number at least 8.