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?

  • $\begingroup$ did you try findstat.org/StatisticFinder?Domain=Cc0020 yet? $\endgroup$ Commented Nov 11, 2021 at 14:17
  • $\begingroup$ 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 $\endgroup$ Commented Nov 11, 2021 at 14:21
  • $\begingroup$ 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. $\endgroup$ Commented Nov 11, 2021 at 17:21

1 Answer 1


Something to start with.

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$.

  • $\begingroup$ this is a great answer, thanks a lot! $\endgroup$ Commented Nov 15, 2021 at 11:23

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.