1
$\begingroup$

For a finite graph, we can find the number of connected components of the graph as $\dim \ker L$, where $L = D - A$ is the Laplacian matrix.

Does this still hold true for an infinite graph where every vertex has finite degree (if we consider the domain and codomain of $L$ to be sequence space $\Bbb{R}^\infty$)?

If not, what about if every vertex has bounded degree (i.e. there exists $M$ so that $d(v) \leq M$ for all $v \in V(G)$)?

Follow-up: Eric Wofsey has given an explicit example where $\dim \ker L$ is strictly greater than the number of connected components. Is it possible to go the other way, and have $\dim \ker L$ be strictly less? Or is $\dim \ker L$ always an upper bound?

Follow-up to the follow-up: How may the number of connected components of an infinite graph with bounded degree, or where every vertex has finite degree, be calculated from its adjacency matrix or its Laplacian matrix?

$\endgroup$
2
  • $\begingroup$ By $\mathbb{R}^\infty$ do you mean the space of all sequences of real numbers? Or just sequences of finite support? $\endgroup$ May 12 at 17:41
  • $\begingroup$ I mean all sequences, not just finitely supported ones. $\endgroup$ May 12 at 17:48
2
$\begingroup$

No. For instance, consider the graph whose vertices are integers with $n$ adjacent to $n-1$ and $n+1$ for each $n$. Then a sequence $s:\mathbb{Z}\to\mathbb{R}$ is in the kernel of the Laplacian iff $s(n)$ is the average of $s(n-1)$ and $s(n+1)$ for each $n$. Now given any two values for $s(0)$ and $s(1)$, you can uniquely determine the values of $s(n)$ for all $n$ by the recurrence $s(n+1)=2s(n)-s(n-1)$ (explicitly, the solutions to this recurrence are the linear sequences $s(n)=an+b$ where $a$ and $b$ are arbitrary parameters). So $\dim\ker L=2$ , even though the graph has only one connected component.

$\endgroup$
2
  • $\begingroup$ Thank you! Is it possible to come up with an example where $\dim \ker L$ is less than the number of connected components? $\endgroup$ May 12 at 18:34
  • 1
    $\begingroup$ Anything that is constant on each connected component will always be in $\ker L$. $\endgroup$ May 12 at 19:52

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.