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.

Improve this question
$\endgroup$
4
  • $\begingroup$ What does "maximal" mean? $\endgroup$
    – Igor Rivin
    Apr 29, 2016 at 16:15
  • $\begingroup$ I clarified what I mean by this in the post, thanks. $\endgroup$
    – ABIM
    Apr 29, 2016 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, 2016 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, 2018 at 16:25

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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