# Laplacian Degrees of a Graph

**Conjecture**If is a connected graph on vertices, then for .

(Reproduced from [M].)

Let be the Laplacian matrix of a graph of order . Let be the -th largest eigenvalue of (). For the purpose of this problem, we call the number the -th *Laplacian degree* of . In addition to that, let be the -th largest (usual) degree in . It is known that every connected graph satisfies for [GM], [LP] and for [G].

## Bibliography

[GM] R. Grone, R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math.7 (1994) 221-229. MathSciNet

[LP] J.S. Li, Y.L. Pan, A note on the second largest eigenvalue of the Laplacian matrix of a graph, Linear Multilin. Algebra 48 (2000) 117-121. MathSciNet

*[G] J.-M. Guo, On the third largest Laplacian eigenvalue of a graph, Linear Multilin. Algebra 55 (2007) 93-102. MathSciNet

[M] B. Mohar, Problem of the Month

* indicates original appearance(s) of problem.

### Equality?

Any conjectures about the structure of the graphs for which equality holds (for any particular value of k)?

Gordon Royle

## Proved

Proved by Willem Haemers and Andries Brouwer, see guo.pdf.