## 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.