Multiplizitäten der Laplace-Eigenwerte eines Graphen

Question

Lassen $\lambda^G_1 > \lambda^G_2 > \dots$ seien die Eigenwerte der Laplace-Matrix $G$ eines Graphen auf $n$ Eckpunkte.

Lassen $\mu(G)$ sei die Zusammensetzung $a_1,\dots,a_k$ von $n$ wo $a_i$ ist die Vielzahl von $\lambda^G_i$.

Ist $\mu$ Surjektiv als Karte von (endlichen) einfachen Graphen zu ganzzahligen Kompositionen?

Answer 1

Wir können tatsächlich einen Graphen mit der gewünschten Zusammensetzung von Multiplizitäten erstellen, indem wir isolierte Eckpunkte hinzufügen und Komplemente nehmen:

Beachten Sie zunächst, dass der kleinste Laplace-Eigenwert eines Graphen $G$ ist $0$ und dass seine Vielfalt ist $1$ dann und nur dann, wenn $G$ Ist verbunden.

Lassen $(a_1,\dots,a_k)$die gewünschte Zusammensetzung sein. Wenn$a_k > 1$können wir ein Diagramm auswählen $G$ mit $\mu(G)=(a_1,\dots,a_{k-1},1)$ und hinzufügen $a_k-1$ isolierte Eckpunkte.

Wenn $a_k = 1$Wählen Sie ein Diagramm $G$ mit $\mu(G) = (a_{k-1},\dots,a_2, a_1+1)$. Dann die Ergänzung von$G$ hat die gewünschten Multiplizitäten.