Is it known for which class of graphs the normalized laplacian has only simple eigenvalues (i.e., with multiplicity one)? In particular, are there trees (or perhaps a specific class of trees) whose normalized laplacian has only simple eigenvalues?


Thanks.



normalized laplacian spectrum of trees
It is a partial answer for your question:


For $P\_n$, the form of normalized laplacian matrix is three diagonal and with some calculations, we can show that all its normalized laplacian eigenvalues are simple. For example, the normalized laplacian spectrum of $P\_n$ for $n=2,3,4,5$ are:


$P\_2:$ $[0,2]$,


$P\_3: [0,1,2]$,


$P\_4: [0,2,\frac{1}{2},\frac{3}{2}]$,


$P\_5: [0,1,2,1-\frac{\sqrt2}{2},1+\frac{\sqrt2}{2}]$.


In the paper with name:


"Eigenvalues of normalized Laplacian matrices of fractal trees and dendrimers: Analytical results and applications",


There are some useful results about fractal and Cayley tree and their normalized laplacian spectrum and their degeneracy. Specially, in section $III$ part $B$, you can find some useful calculation. For example, the fractal $F\_1$ for $m=0$ has simple normalized spectrum and is an other example for your question. I wrote a Maple program that can calculate the requested spectrum. If it is useful, I can send it for you.


I tested many trees up to 10 vertices with package RandomTree in Maple, and it seems $star like$ trees have the property that you want. These graphs are interesting, since they studied a lot for determining are they $DS$ or not.


Also, since almost all trees have diameter 2 and these trees are $star$, so almost all trees do not have the property that you want. In contrast, a lot of trees up to 10 vertices have the property that you want.


