Laplacian Degrees of a Graph

Let L = D - A be the Laplacian matrix of a graph G of order n. Let t_k be the kth largest eigenvalue of L (k = 1,...,n). For the purpose of this month's problem, we call the number

         c_k = c_k(G) = t_k + k - 2

the kth Laplacian degree of G. In addition to that, let d_k(G) be the kth largest (usual) degree in G. It is known that every connected graph satisfies c_k(G) ≥ d_k(G) for k = 1 [1], k = 2 [2] and for k = 3 [3].

Conjecture 1 (Guo [3]): If G is a connected graph on n vertices, then c_k(G) ≥ d_k(G) for k = 1,2,...,n-1.

Bibliography:

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

[2] 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.

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

Send comments to mohar@sfu.ca

Revised: January 12, 2007.