# Laplacian Degrees of a Graph

 Importance: Medium ✭✭
 Author(s): Guo, Ji-Ming
 Subject: Graph Theory » Algebraic Graph Theory
 Keywords: degree sequence Laplacian matrix
 Recomm. for undergrads: no
 Posted by: Robert Samal on: June 22nd, 2007
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.

### Proved

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

### Equality?

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

Gordon Royle

## Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.