Two relevant Math Overflow questions: mathoverflow.net/questions/136805/… and mathoverflow.net/questions/136434/… .

Thanks. Very interesting. I've have Spectral Graph Theory by Fan R. K. Chung to read when I find the time. What about the eigenvectors of the Laplacian? Do they have any interpretation? I know that the eigenvector of matrix $W$ associated with eigenvalue $1$ is the stationary distribution of a random walk of the graph (the graph has to satisfy some conditions; see Peron-Frobenius theorem). What about the other eigenvectors?

A link that may be interesting. I have not looked into it in great detail. orion.math.iastate.edu/butler/PDF/dissertation.pdf

Granted that the adjacency matrix of an undirected graph can be coded as a $(0, 1)$-matrix. But why should the eigenvalues of the Laplacian have anything to do with connectivity? Why should the spectrum of the Laplacian tell you so much about the graph? It seems surprising to me.

Somewhat related Math Overflow post: mathoverflow.net/questions/58721/…