Partition density, star arboricity, and sums of Laplacian eigenvalues of graphs

Let $G=(V,E)$ be a graph on $n$ vertices, and let ${\lambda }_1(L(G))\ge \cdots \ge {\lambda }_{n-1}(L(G))\ge {\lambda }_n(L(G))=0$ be the eigenvalues of its Laplacian matrix $L(G)$. Brouwer conjectured that for every $1\le k\le n$, ${\sum }_{i=1}^k{\lambda }_i(L(G))\le \mathrm{\mid }E\mathrm{\mid }+\left(\genfrac{}{}{0px}{}{k+1}{2}\right)$. Here, we prove the following weak version of Brouwer’s conjecture: For every $1\le k\le n$, $$\sum _{i=1}^k{\lambda }_i(L(G))\le \mathrm{\mid }E\mathrm{\mid }+k^2+15k\log k+65k\mathrm{.}$$ For a graph $G=(V,E)$, we define its partition density $\tilde{\rho }(G)$ as the maximum, over all subgraphs $H$ of $G$, of the ratio between the number of edges of $H$ and the number of vertices in the largest connected component of $H$. Our argument relies on the study of the structure of the graphs $G$ satisfying $\tilde{\rho }(G)<k$. In particular, using a result of Alon, McDiarmid and Reed, we show that every such graph can be decomposed into at most $k+15\log k+65$ edge-disjoint star forests (that is, forests whose connected components are all isomorphic to stars). In addition, we show that for every graph $G=(V,E)$ and every $1\le k\le \mathrm{\mid }V\mathrm{\mid }$, $$\sum _{i=1}^k{\lambda }_i(L(G))\le \mathrm{\mid }E\mathrm{\mid }+k\cdot \nu (G)+\lfloor \frac{k}{2}\rfloor ,$$ where $\nu (G)$ is the maximum size of a matching in $G$.