A majorization bound for the eigenvalues of some graph Laplacians

Abstract

It is conjectured that the Laplacian spectrum of a graph is majorized by its conjugate degree sequence. In this paper, we prove that this majorization holds for a class of graphs including trees. We also show that a generalization of this conjecture to graphs with Dirichlet boundary conditions is equivalent to the original conjecture.

9 pages