Graph Limits and Spectral Extremal Problems for Graphs

.We prove two conjectures in spectral extremal graph theory involving the linear combinations of graph eigenvalues. Let \(\lambda_1(G)\) be the largest eigenvalue of the adjacency matrix of a graph \(G\) and \(\overline{G}\) be the complement of \(G\). A nice conjecture states that the graph on \(n\) vertices maximizing \(\lambda_1(G) + \lambda_1(\overline{G})\) is the join of a clique and an independent set with \(\lfloor n/3\rfloor\) and \(\lceil 2n/3\rceil\) (also \(\lceil n/3\rceil\) and \(\lfloor 2n/3\rfloor\) if \(n \equiv 2 \pmod{3}\)) vertices, respectively. We resolve this conjecture for sufficiently large \(n\) using analytic methods. Our second result concerns the \(Q\)-spread of a graph \(G\), which is defined as the difference between the largest eigenvalue and least eigenvalue of the signless Laplacian of \(G\). It was conjectured by Cvetković, Rowlinson, and Simić [Publ. Inst. Math., 81 (2007), pp. 11–27] that the unique \(n\)-vertex connected graph of maximum \(Q\)-spread is the graph formed by adding a pendant edge to \(K_{n-1}\). We confirm this conjecture for sufficiently large \(n\).KeywordsNordhaus–Gaddum inequalityspectral radiusgraphon\(Q\)-spreadMSC codes05C5015A18