3
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ It barely works for $n=3$! $\endgroup$ Sep 3, 2020 at 14:00

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
6
  • 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, 2020 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, 2020 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, 2020 at 17:34
  • $\begingroup$ This reminds me of "The critical group of a threshold graph" Hans Christianson and Victor Reiner. Connection? $\endgroup$ Sep 3, 2020 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, 2020 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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