Is there a way to count the number of vertices in a connected subgraph S that is part of a larger, disconnected graph G?

Question

I apologize a head of time if this has been answered elsewhere. I have a random graph G, and this graph is disconnected and contains a unknown number of connected subgraphs (not all vertices in G's vertex set will be contained in the union of all subgraph's vertex sets though). I have calculated the Laplacian of G (and the adjacency matrix of G), and its corresponding eigen-spectrum, and therefore have easy access to the number of connected subgraphs contained within G. My question is, apart from employing a brute-force counting algorithm where I loop over all vertices and edges, is there an efficient way to calculate the number of vertices contained within each connected subgraph, given only the adjacency matrix, Laplacian, and the eigen-spectrum of either the adjacency matrix and/or Laplacian? I can provide any further information if needed. Thank you.

Answer 1

The information about the connected components is contained in the eigenvectors of the Laplacian eigenvalue $\lambda_0 = 0$ (the smallest eigenvalue); in other words, in the null space of the Laplacian matrix $L$.

For all graphs, the vector $\mathbf v = (1,1,\dots,1)$ satisfies $L\mathbf v = \mathbf 0$, and for connected graphs, that's the only eigenvector. In general, if the connected components of $G$ have vertex sets $V_1, V_2, \dots, V_k$, then there are $k$ eigenvectors of $0$: for each component $V_i$, its indicator vector (the vector $\mathbf v$ with $v_j = 1$ if $j \in V_i$, and $v_j = 0$ otherwise) is an eigenvector.

Of course, you might not necessarily get this particular basis for the null space. (You might, since it's a very natural one!) However, in general, this will be the only "column-reduced" basis. So if you have a basis $\mathbf v^{(1)}, \dots, \mathbf v^{(k)}$ for the null space of $L$, then you can row-reduce the $k \times n$ matrix with rows $(\mathbf v^{(1)})^{\mathsf T}, \dots, (\mathbf v^{(k)})^{\mathsf T}$. The rows of the row-reduced matrix will give you another basis for the null space: the one that tells you what the components are.

Once you have that basis, you can just count the number of $1$'s in each vector to find the number of vertices in each connected component.

---

A note on efficiency: for a general graph, it is actually faster to do some graph algorithm like breadth-first or depth-first search. These run in $O(n^2)$ time, while the Gaussian elimination needed to find the null space is $O(n^3)$. So using the eigenvectors as I've outlined above is only a good idea if, indeed, you already needed to compute them for something else.

Additionally, if you have a sparse graph with many connected components, graph algorithms become more efficient, while the $k \times n$ row reduction I'v described becomes less efficient, so it might not be a good idea to use the eigenvectors even if you have them - unless they're already in reduced form.