# number of components of subgraphs

Given a finite simple graph $$G$$ with $$n$$ vertices, for each 0-1 colouring $$\alpha \in \mathbb{Z}_2^n$$ of its vertices consider the subgraph $$G_\alpha$$, whose vertices are the $$1$$-coloured vertices in $$\alpha$$, created as follows: if two vertices with labels $$1$$ are adjacent, then add the edge between them. Is there a way of computing $$\Theta(G) = \sum_{k = 1}^n (-1)^k \sum_{\substack{\alpha \in 2^n\\|\alpha|= k}} \# G_\alpha,$$ where $$|\alpha|$$ is the sum of the components of $$\alpha$$ (so the number of vertices with label $$1$$) and $$\#G_\alpha$$ is the number of connected components of $$G_\alpha$$.

As an example, for complete graphs we have $$\Theta(K_m)= -1$$.

Are the values of $$\Theta$$ known at least on simple families of graphs, such as the cycle graphs or the $$1$$-skeletons of the $$m$$-dimensional cubes?

• did you try findstat.org/StatisticFinder?Domain=Cc0020 yet? Commented Nov 11, 2021 at 14:17
• no, wasn't aware of this webpage, will check it out, but at a first glance it doesn't seem to cover topics specifically related to this problem Commented Nov 11, 2021 at 14:21
• what I meant is, if you plug in the first few numbers, and you are lucky, you will find that someone has studied your statistic already. Commented Nov 11, 2021 at 17:21

We have $$\Theta(G)=\sum_{\alpha} (-1)^{\alpha}\#G_\alpha=\sum_{\alpha}(-1)^\alpha\sum_U \mathbf{1}(U\,\text{is a component of}\,G_{\alpha}),$$ where $$U$$ runs over all induced connected subgraphs of $$G$$. Changing the order of summation, we get $$\Theta(G)=\sum_U \sum_{\alpha:\, U\,\text{is a component of}\,G_{\alpha}} (-1)^{\alpha}.$$ Look at the inner sum. Let $$\tilde{U}$$ denote the set of vertices $$v\in V\setminus U$$ (here $$V=$$set of vertices of $$G$$), which have a neighbour in $$U$$, and $$U^*$$ denote $$V\setminus (U\cup \tilde{U})$$. Then $$G_\alpha$$ must contain $$U$$, should not have vertices in $$\tilde{U}$$ and may contain arbitrary subset of $$U^*$$. It yields that the inner sum has $$2^{|U^*|}$$ summands, and that it vanishes unless $$U^*=\emptyset$$. In the latter case, the inner sum equals $$(-1)^{|U|}$$. Such $$U$$ for which $$U^*=\emptyset$$ (that is, every vertex either belongs to $$U$$ or has a neighbour in $$U$$) are called dominating. Thus $$\Theta(G)=\sum_{U\,\text{is dominating and connected}} (-1)^{|U|}.$$ If $$G=C_n$$ is a cycle of length $$n$$, then $$U$$ should be either the whole cycle (1 variant), or a path of length $$n-1$$ ($$n$$ variants) or a path of length $$n-2$$ ($$n$$ variants), so we get $$\Theta(C_n)=(-1)^n$$.