# The number of dominating sets of a bipartite graph is not exactly divisible by $2$

here is a cute problem I created from another cute problem. Prove the number of dominating sets of a bipartite graph is never exactly divisible by $2$.

A dominating set of a graph is a set of vertices $D$ such that every vertex not in $D$ is adjacent to at least one vertex in $D$

Regards.

• i'm not quite sure yet but it seems to me that mapping each dominating set to the set of vertices that are neighbors of at least one element of the dominating set gives us a bijection between dominating sets. it would have to be shown though that this really is a bijection and that only the set that contains all the vertices is mapped to itself. – Dániel G. Jun 19 '14 at 19:25
• What about $K_2$ ? It's bipartite, and has 2 dominating sets. Or, do you count $V$ as a dominating set ? – Manuel Lafond Jun 19 '14 at 20:14
• @manuellafond I think $V(G)$ is a dominating set by default based on the definition given. – Perry Elliott-Iverson Jun 19 '14 at 20:28
• Yes, $V$ is a dominating set, it satisfies the condition vacuosly. – Jorge Jun 19 '14 at 20:37
• Of course :) That's a fun problem indeed. So, have you solved it and posted to share, or are you also looking for an answer ? – Manuel Lafond Jun 20 '14 at 1:51

This is actually true for all graphs $G$, and can be proven by considering the Domination Polynomial of a graph; $D(G,x) := \sum_{k=0}^{|V(G)|} d_k(G) x^k$ where $d_k(G)$ is the number of dominating sets of cardinality $k$ in $G$.
Your problem is thus to show that $D(G,1) \equiv 1 \mod 2$. We proved it as a corollary to another result in Subset-Sum Representations of Domination Polynomials. (Graphs Combin. 30 (2014), no. 3, 647–660.)
$$D(G, x) = xD(G/u, x) + D(G − u, x) + xD(G − N[u], x) − (1 + x)p_u(G, x)$$
When we substitute $x=1$ into this you can see that the last term is even and thus there are 3 terms belonging to smaller graphs which are necessarily odd by the induction hypothesis; 3 odd numbers added makes an odd number.