A proof of the maximum Laplacian energy conjecture for connected graphs via a sharp eigenvalue-sum bound

Abstract

Let $S_k(G)$ denote the sum of the $k$ largest Laplacian eigenvalues of a connected graph $G$ of order $n$ and size $m$. Write ${\mathrm{PA}}_{n,\omega }$ for the graph obtained from an $\omega$-vertex clique by attaching $n-\omega$ pendant vertices to one of its vertices, and set \[ M_{n,k}:=\binom{k+1}{2}+n-k-1, \] the number of edges of ${\mathrm{PA}}_{n,k+1}$. For $n/2<k\le n-2$, we prove the sharp bound \[ S_k(G)\le \frac{2k}{n}m+ \frac{2(n-k)}{n}M_{n,k}-(n-k-1), \] with equality attained by ${\mathrm{PA}}_{n,k+1}$. This bound is complementary to Brouwer's inequality and is strictly stronger when $m<M_{n,k}$. Combining our bound with Brouwer's inequality, we resolve and strengthen a conjecture of Vinagre, Del-Vecchio, Justo, and Trevisan: for every $n$, the pineapple ${\mathrm{PA}}_{n,1+\lfloor 2n/3\rfloor }$ maximizes the Laplacian energy among all connected graphs of order $n$; moreover, for $n>4$, it is the unique maximizer.

arXiv comment12 pages