Is there a class of graphs (besides the path graphs) for which we know that the Laplacian L = D - A (where D is the degree matrix and A is the adjacency matrix) has simple spectrum, i.e. all Laplacian eigenvalues have multiplicity 1?
2
-
$\begingroup$ For a while, we were not sure you existed! $\endgroup$– Baby DragonCommented Jul 12, 2013 at 20:34
-
$\begingroup$ Roughly speaking, this is probably true for almost all graphs: mathoverflow.net/questions/128265/… $\endgroup$– Felix GoldbergCommented Jul 22, 2013 at 10:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
For a start, there's the complements of the paths. (If the Laplacian eigenvalues of a graph are all simple, then so are the eigenvalues of its complement.) Most regular graphs have only simple eigenvalues; in particular if my sage computations can be trusted then 6 of 21 cubic graphs on 10 vertices have only simple eigenvalues.
answered Jul 12, 2013 at 19:31
-
2$\begingroup$ Just to complement Chris's answer: Eigenspaces of $L$ are representation spaces of the automorphism group of the graph. So a graph with many symmetries is likely to have eigenvalues of high multiplicity. $\endgroup$ Commented Jul 12, 2013 at 21:09