Laplacian spectrum and size of a graph

Question

Does the Laplacian spectrum of a graph give information on the size of the graph?

For example, is it possible that I have two disconnected graphs $G$ and $H$ with the following features:

1) $G$ and $H$ have the same Laplacian spectrum,

2) $G$ and $H$ have the same size,

3) $G$ and $H$ have two components such that $A$ and $B$ are the components of $G$ and both have the same size, and $C$ and $D$ are components of $H$ with different sizes.

Answer 1

Well, yes, the Laplacian spectrum does determine the size of the graph, depending on what precisely you mean by "Laplacian" and "size".

• If you think of the Laplacian as $L = D - A$ (degree matrix and adjacency matrix) then the sum of the eigenvalues of $L$ is the trace of $L$ which is just the sum of the degrees of the vertices which in turn is twice the number of edges.
• If you prefer the normalized laplacian $L = D^{-1/2}(D - A)D^{-1/2}$ then the diagonal entries are all $1$, so the sum of the eigenvalues of $L$ is the trace of $L$ which is the number of vertices.

Regarding your other question, I'm not sure if you can recover the size of a component of $G$ from only the spectrum of $G$, but certainly if $G$ has two connected components then the Laplacian matrix is block diagonal, and as above you can recover the size of a component from the spectrum of the corresponding block.

Answer 2

If $A$ is the adjacency matrix, and $D$ is the diagonal degree matrix, then the matrix $P= D^{-1}A$ governs the natural random walk on the graph: at each vertex the walker is equally likely to follow any edge at that vertex. If the graph is disconnected, the corresponding Markov chain is not irreducible, and the irreducible components of the random walk correspond to the components of the graph. The number of components is the dimension of eigenspace of $P^*$ corresponding to the eigenvalue $1$.

To determine the component containing at a given vertex use a Monte Carlo simulation to start the random walk at that vertex and see where it leads you. If you run the walk for a long time you will hit, with high confidence, all the vertices of that component, and no other.