Convex functions on graphs: Sum of the eigenvalues

Abstract

Let $G$ be a simple graph with the Laplacian matrix $L(G)$ and let $e(G)$ be the number of edges of $G$. A conjecture by Brouwer and a conjecture by Grone and Merris state that the sum of the $k$ largest Laplacian eigenvalues of $G$ is at most $e(G)+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)$ and ${\sum }_{i=1}^k{d}_i^{\ast }$, respectively, where $(d_i^{\ast }{)}_i$ is the conjugate of the degree sequence $(d_i{)}_i$. We generalize these conjectures to weighted graphs and symmetric matrices. Moreover, among other results we show that under some assumptions, concave upper bounds on convex functions of symmetric real matrices are equivalent to concave upper bounds on convex functions of $(0,1)$ matrices.

17 pages, 6 figures