Grinberg-Introduction-Graph-Theory · Problem 5.4

Trees and arborescences

Mathematics — Graph Theory · forests-dominating-sets

Problem

A dominating set of a multigraph GG is defined to be a dominating set of its underlying simple graph GsimpG^{\mathrm{simp}}. Let GG be a forest. Prove that ∑D is a dominating set of G(−1)∣D∣=±1.\sum_{D \text{ is a dominating set of } G} (-1)^{|D|} = \pm 1.

Browse the problem library