Let $\lambda^G_1 > \lambda^G_2 > \dots$ be the eigenvalues of the Laplacian matrix $G$ of a graph on $n$ vertices.

Let $\mu(G)$ be the composition $a_1,\dots,a_k$ of $n$ where $a_i$ is the multiplicity of $\lambda^G_i$.

Is $\mu$ surjective as a map from (finite) simple graphs to integer compositions?

  • 2
    $\begingroup$ It barely works for $n=3$! $\endgroup$ Sep 3 '20 at 14:00

We can actually construct a graph with the desired composition of multiplicities by adding isolated vertices and taking complements:

As an initial remark, note that the smallest Laplacian eigenvalue of a graph $G$ is $0$ and that its multiplicity is $1$ if and only if $G$ is connected.

Let $(a_1,\dots,a_k)$ be the desired composition. If $a_k > 1$, we can choose a graph $G$ with $\mu(G)=(a_1,\dots,a_{k-1},1)$ and add $a_k-1$ isolated vertices.

If $a_k = 1$, choose a graph $G$ with $\mu(G) = (a_{k-1},\dots,a_2, a_1+1)$. Then the complement of $G$ has the desired multiplicities.

  • 2
    $\begingroup$ (For people like me who are a bit slow, regarding the last paragraph: since $a_1+1 > 1$, the graph $G$ is disconnected; hence its complement is connected; hence $\lambda_1^{G} < n$; and so indeed the complement of $G$ has the desired $\mu$.) $\endgroup$ Sep 3 '20 at 16:00
  • $\begingroup$ I believe it also follows from your argument that to get all the compositions we only need to consider threshold graphs: en.wikipedia.org/wiki/Threshold_graph $\endgroup$ Sep 3 '20 at 17:29
  • 3
    $\begingroup$ Note, interestingly, that the number of isomorphism classes of threshold graphs on $n$ vertices is $2^{n-1}$, the same as the number of compositions of $n$. I guess your construction gives a bijection between these sets. $\endgroup$ Sep 3 '20 at 17:34
  • $\begingroup$ This reminds me of "The critical group of a threshold graph" Hans Christianson and Victor Reiner. Connection? $\endgroup$ Sep 3 '20 at 18:42
  • $\begingroup$ Theorem 5 of that paper (doi.org/10.1016/S0024-3795(02)00252-5) says "The eigenvalues of L(G) for G a threshold graph are the column lengths of the Ferrers diagram of the degree sequence of G," which is directly related to your eigenvalues multiplicity question. They attribute that result to Merris (doi.org/10.1016/0024-3795(94)90361-1). But I don't know if there's a direct connection to critical groups. $\endgroup$ Sep 3 '20 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.