Laplacian Degrees of a Graph

Importance: Medium ✭✭
Author(s): Guo, Ji-Ming
Recomm. for undergrads: no
Posted by: Robert Samal
on: June 22nd, 2007

\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].


[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]{}

* indicates original appearance(s) of problem.


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


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.