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

Abstract

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 |E|+\left(\genfrac{}{}{0ex}{}{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 λ_i(L(G)) \leq |E|+k^2+15k\log{k}+65k. \] 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 |V|$, \[ \sum_{i=1}^k λ_i(L(G)) \leq |E|+k\cdot ν(G) + \left\lfloor\frac{k}{2}\right\rfloor, \] where $\nu (G)$ is the maximum size of a matching in $G$.