Let L = D - A be the Laplacian matrix of a graph G of order n. Let tk be the kth largest eigenvalue of L (k = 1,...,n). For the purpose of this month's problem, we call the number
ck = ck(G) = tk + k - 2
the kth Laplacian degree of G. In addition to that, let dk(G) be the kth largest (usual) degree in G. It is known that every connected graph satisfies ck(G) ≥ dk(G) for k = 1 , k = 2  and for k = 3 .
Conjecture 1 (Guo ): If G is a connected graph on n vertices, then ck(G) ≥ dk(G) for k = 1,2,...,n-1.
 R. Grone, R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math.7 (1994) 221-229.
 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.
 J.-M. Guo, On the third largest Laplacian eigenvalue of a graph, Linear Multilin. Algebra 55 (2007) 93-102.
Send comments to email@example.com