Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
For a while, we were not sure you existed! –  Baby Dragon Jul 12 '13 at 20:34
    
Roughly speaking, this is probably true for almost all graphs: mathoverflow.net/questions/128265/… –  Felix Goldberg Jul 22 '13 at 10:35
add comment

1 Answer

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.

share|improve this answer
2  
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. –  Alain Valette Jul 12 '13 at 21:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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