Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues

Lele Liu

Published 2022-06-08Version 1

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 $\bar{G}$ be the complement of $G$. A nice conjecture states that the graph on $n$ vertices maximizing $\lambda_1(G) + \lambda_1(\bar{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 $s_Q(G)$ 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\'c, Rowlinson and Simi\'c in $2007$ 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$.