I know that we can determine the number of connected components of a graph from the eigenvalues of its Laplacian matrix. My question is:
Is there a way to understand the size of each connected component of a graph from its eigenvalues?
For example: if a graph has 3 connected components two of which are maximal then can we determine this from the graph's spectrum?
Explanation of terminology:
By maximal connected component, I mean a connected component whose number of nodes at least greater (not strictly) than the number of nodes in every other connected component in the graph.
Best Answer
This isn't possible; here is some intuition. If $G$ is a graph with $k$ components, then the multiplicity of 0 as an eigenvalue is $k$. This is because we can write $$L=\begin{pmatrix} L_1 & & \\ & \ddots & \\ & & L_k \end{pmatrix}$$ where $L$ is the Laplacian for $G$, and $L_i$ is the Laplacian for the $i$-th component. Each $L_i$, as the Laplacian of a connected graph, has eigenvalue 0 with multiplicity 1. Since the components can be chosen independently, it seems very unlikely that the sizes of these blocks $L_i$ would be uniquely determined by the union of their spectra.
I believe the following provides a counterexample in the specific case you asked about (but be sure to check my work):
$G_1$ is the disjoint union of a 3-cycle with an extra node attached to one of the corners, two 3-cycles which share an edge, and a single node.
$G_2$ is the union of a complete graph on 4 nodes, a 3-path, and a 2-path.
I believe both of these have spectrum $\{4,4,4,3,2,1,0,0,0\}$. However $G_1$ has two maximal components while $G_2$ does not.