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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

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

Zoran Stanić, Haiying Shan, Muhuo Liu, Chaohui Chen
The Electronic Journal of Combinatorics
Graph theory and applications
article

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

Zoran Stanić, Haiying Shan, Muhuo Liu, Chaohui Chen
article en

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.

The Electronic Journal of CombinatoricsVol. 32(2)
South China Agricultural University (CN), Tongji University (CN), University of Belgrade (RS), Department of Mathematical Sciences (RU), China Agricultural University (CN)
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
Openalex Percentile: Top 87%
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.