4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What does "maximal" mean? $\endgroup$ – Igor Rivin Apr 29 '16 at 16:15
  • $\begingroup$ I clarified what I mean by this in the post, thanks. $\endgroup$ – AIM_BLB Apr 29 '16 at 16:21
  • $\begingroup$ @CSA The order of the maximal connected component can be obtained from the eigenvectors (specifically the null vectors) of the Laplacian. If you choose the null vectors that have disjoint support, then it is easy to see that the largest $\ell_0$ "norm" of these vectors is the order of the maximal component. $\endgroup$ – S.B. Sep 7 '16 at 23:31
  • $\begingroup$ @S.B. Can you clarify--the number of nodes in the largest component of the graph is equal to the largest eigenvalue? I stumbled on this post looking for a proof for such a property. But I don't get what you say about null vectors and disjoint support. How do I find the order of the largest connected component? $\endgroup$ – Peter Mitrano Apr 21 '18 at 16:25
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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