Geodesic
Graphs with large clique number whose second largest eigenvalue does not exceed \((\sqrt{5}-1)/2\)
Muhuo Liu1 ; Chaohui Chen2 ; Zoran Stanić3 ; Haiying Shan4
1Department of Mathematics, South China Agricultural University
2School of Mathematical Sciences, Tongji University
3Faculty of Mathematics, University of Belgrade
4Tongji University
The electronic journal of combinatorics, Tome 32 (2025) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/13017
Classification : 05C50, 05C69, 15A18
Mots-clés : clique number, largest eigenvalue, golden section

Muhuo Liu  1   ; Chaohui Chen  2   ; Zoran Stanić  3   ; Haiying Shan  4

1 Department of Mathematics, South China Agricultural University
2 School of Mathematical Sciences, Tongji University
3 Faculty of Mathematics, University of Belgrade
4 Tongji University 
@article{10_37236_13017,
     author = {Muhuo Liu and Chaohui Chen and Zoran Stani\'c and Haiying Shan},
     title = {Graphs with large clique number whose second largest eigenvalue does not exceed \((\sqrt{5}-1)/2\)},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {2},
     doi = {10.37236/13017},
     zbl = {1564.05197},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/13017/}
}
TY  - JOUR
AU  - Muhuo Liu
AU  - Chaohui Chen
AU  - Zoran Stanić
AU  - Haiying Shan
TI  - Graphs with large clique number whose second largest eigenvalue does not exceed \((\sqrt{5}-1)/2\)
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/13017/
DO  - 10.37236/13017
ID  - 10_37236_13017
ER  - 
%0 Journal Article
%A Muhuo Liu
%A Chaohui Chen
%A Zoran Stanić
%A Haiying Shan
%T Graphs with large clique number whose second largest eigenvalue does not exceed \((\sqrt{5}-1)/2\)
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/13017/
%R 10.37236/13017
%F 10_37236_13017
Muhuo Liu; Chaohui Chen; Zoran Stanić; Haiying Shan. Graphs with large clique number whose second largest eigenvalue does not exceed \((\sqrt{5}-1)/2\). The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/13017

Cité par Sources :