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.