Graphs with Large Clique Number whose Second Largest Eigenvalue does not Exceed $(\sqrt{5}-1)/2$
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.
Authors
- Zoran Stanić (ORCID: https://orcid.org/0000-0002-4949-4203)
- Haiying Shan (ORCID: https://orcid.org/0000-0002-2749-9476)
- Muhuo Liu (ORCID: https://orcid.org/0000-0001-8217-2452)
- Chaohui Chen (ORCID: https://orcid.org/0000-0002-9089-257X)
Institutions
- South China Agricultural University (CN)
- Tongji University (CN)
- University of Belgrade (RS)
- Department of Mathematical Sciences (RU)
- China Agricultural University (CN)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2025-04-24
- DOI
- https://doi.org/10.37236/13017
- Primary Topic
- Graph theory and applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Natural Science Foundation of China
- Natural Science Foundation of Guangdong Province
- Science Fund of the Republic of Serbia
- Fundamental Research Funds for the Central Universities