A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size (Q2668072)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size |
scientific article |
Statements
A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size (English)
0 references
3 March 2022
0 references
\textit{M. Zhai} et al. [Eur. J. Comb. 95, Article ID 103322, 18 p. (2021; Zbl 1475.05113)] proved that if a graph \(G\) is \(C_5\)-free of size \(m\ge 8\) or \(C_6\)-free of size \(m\ge 22\), then its spectal radius \(\rho(G)\) satisfies \(\rho(G)\le \frac{1+\sqrt{4m-3}}{2}\) with equality exactly when \(G\) is the book \(S_{\frac{m+3}{2},2}\). So, when \(m\) is even, the bound they found is not sharp. Inspired by this result, the authors prove in the paper under review that if \(G\) is \(C_5\)-free of even size \(m\ge 14\) or \(C_6\)-free of even size \(m\ge 74\), the maximum of \(\rho(G)\) is attained when \(G\) is the graph obtained from the book \(S_{\frac{m+4}{2},2}\) by deleting an edge incident to a vertex of degree two. The key idea of the proof is to look at the neighbors of the vertex corresponding the maximum entry of the Perron vector of the graph attaining the maximal spectral radius.
0 references
spectral radius
0 references
adjacency matrix
0 references