Subset-Sum Representations of Domination Polynomials

Abstract

The domination polynomial D(G, x) is the ordinary generating function for the dominating sets of an undirected graph G = (V, E) with respect to their cardinality. We consider in this paper representations of D(G, x) as a sum over subsets of the edge and vertex set of G. One of our main results is a representation of D(G, x) as a sum ranging over spanning bipartite subgraphs of G. Let d(G) be the number of dominating sets of G. We call a graph G conformal if all of its components are of even order. Let Con(G) be the set of all vertex-induced conformal subgraphs of G and let k(G) be the number of components of G. We show that

$$d(G) = \sum \limits_{H\in{\rm Con}(G)}2^{k(H)}$$

.