5
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – Dániel G. Jun 19 '14 at 19:25
  • $\begingroup$ What about $K_2$ ? It's bipartite, and has 2 dominating sets. Or, do you count $V$ as a dominating set ? $\endgroup$ – Manuel Lafond Jun 19 '14 at 20:14
  • $\begingroup$ @manuellafond I think $V(G)$ is a dominating set by default based on the definition given. $\endgroup$ – Perry Elliott-Iverson Jun 19 '14 at 20:28
  • $\begingroup$ Yes, $V$ is a dominating set, it satisfies the condition vacuosly. $\endgroup$ – Jorge Jun 19 '14 at 20:37
  • $\begingroup$ 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 ? $\endgroup$ – Manuel Lafond Jun 20 '14 at 1:51
3
$\begingroup$

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

It can also be shown by induction using this recurrence from Recurrence relations and splitting formulas for the domination polynomial: (Electron. J. Combin. 19 (2012), no. 3, Paper 47)

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

The first proofs we found of this result were published by Andries E. Brouwer: The number of dominating sets of a finite graph is odd.

$\endgroup$

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.