Laplacian Degrees of a Graph

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a finite connected simple graph $G$ on $n$ vertices, let $A$ be its adjacency matrix, $D$ the diagonal matrix of degrees, and $L=D-A$ its Laplacian. Order its eigenvalues as $t_1\ge\cdots\ge t_n$, and degrees as $d_1\ge\cdots\ge d_n$. Put $c_k=t_k+k-2$.

Statement recorded in the supplied source.

The source's recorded conjecture is \[c_k\ge d_k\qquad(1\le k\le n-1).\] Its discussion also asks for a structural characterization of the graphs attaining equality, for each particular index $k$. [S2]

Short English statement

Must every Laplacian degree dominate the corresponding usual degree, and which connected graphs achieve equality?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3148 (OPG-407). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Laplacian Degrees of a Graph, original node 407, statement and mathematical discussion. https://www.openproblemgarden.org/op/laplacian_degrees_of_a_graph.