DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

On the Grone-Merris conjecture

Tamon Stephen


Grone and Merris [GM94] conjectured that the Laplacian spectrum of a graph is majorized by its conjugate vertex degree sequence. We prove that this conjecture holds for a class of graphs including trees. We also show that this conjecture and its generalization to graphs with Dirichlet boundary conditions are equivalent.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional