On a conjecture of spectral extremal problems

• Published in: arXiv.org 2022-03
• Main Authors: Wang, Jing, Kang, Liying, Xue, Yusai
• Format: Article
• Language: English
• Subjects: Apexes; Graph theory; Graphs; Spectra
• ISSN: 2331-8422

For a simple graph \(F\), let \(\mathrm{Ex}(n, F)\) and \(\mathrm{Ex_{sp}}(n,F)\) denote the set of graphs with the maximum number of edges and the set of graphs with the maximum spectral radius in an \(n\)-vertex graph without any copy of the graph \(F\), respectively. The Turán graph \(T_{n,r}\) is the complete \(r\)-partite graph on \(n\) vertices where its part sizes are as equal as possible. Cioabă, Desai and Tait [The spectral radius of graphs with no odd wheels, European J. Combin., 99 (2022) 103420] posed the following conjecture: Let \(F\) be any graph such that the graphs in \(\mathrm{Ex}(n,F)\) are Tur\'{a}n graphs plus \(O(1)\) edges. Then \(\mathrm{Ex_{sp}}(n,F)\subset \mathrm{Ex}(n,F)\) for sufficiently large \(n\). In this paper we consider the graph \(F\) such that the graphs in \(\mathrm{Ex}(n, F)\) are obtained from \(T_{n,r}\) by adding \(O(1)\) edges, and prove that if \(G\) has the maximum spectral radius among all \(n\)-vertex graphs not containing \(F\), then \(G\) is a member of \(\mathrm{Ex}(n, F)\) for \(n\) large enough. Then Cioabă, Desai and Tait's conjecture is completely solved.