Tamon Stephen - On the Grone-Merris conjecture

dmtcs:3395 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3395
On the Grone-Merris conjectureConference paper

Authors: Tamon Stephen 1

  • 1 Department of Computing and Software


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.

https://doi.org/10.46298/dmtcs.3395
Source: HAL:hal-01184351v1
Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] graph Laplacian, majorization, graph spectrum, degree sequence

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 383 times.
This article's PDF has been downloaded 458 times.