# Laplacian Degrees of a Graph

\begin{conjecture} If $G$ is a connected graph on $n$ vertices, then $c_k(G) \ge d_k(G)$ for $k = 1, 2, \dots, n-1$. \end{conjecture}

(Reproduced from [M].)

Let $L = D - A$ be the \Def{Laplacian matrix} of a graph $G$ of order $n$. Let $t_k$ be the $k$-th largest eigenvalue of $L$ ($k = 1,\dots,n$). For the purpose of this problem, we call the number $$ c_k = c_k(G) = t_k + k - 2 $$ the $k$-th \emph{Laplacian degree} of $G$. In addition to that, let $d_k(G)$ be the $k$-th largest (usual) degree in $G$. It is known that every connected graph satisfies $c_k(G) \ge d_k(G)$ for $k = 1$ [GM], $k = 2$ [LP] and for $k = 3$ [G].

## Bibliography

[GM] R. Grone, R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math.7 (1994) 221-229. \MRhref{MR1271994}

[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. \MRhref{MR1813439}

*[G] J.-M. Guo, On the third largest Laplacian eigenvalue of a graph, Linear Multilin. Algebra 55 (2007) 93-102. \MRhref{MR2281876}

[M] B. Mohar, \href[Problem of the Month]{http://www.fmf.uni-lj.si/~mohar/Problems/P0612_LaplacianDegrees.html}

* indicates original appearance(s) of problem.

### Equality?

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

Gordon Royle

## Proved

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