Title: Counting Dominating Sets of Graphs,
Abstract: Counting dominating sets in a graph $G$ is closely related to the
neighborhood complex of $G$. We exploit this relation to prove that the number
of dominating sets $d(G)$ of a graph is determined by the number of complete
bipartite subgraphs of its complement. More precisely, we state the following.
Let $G$ be a simple graph of order $n$ such that its complement has exactly
$a(G)$ subgraphs isomorphic to $K_{2p,2q}$ and exactly $b(G)$ subgraphs
isomorphic to $K_{2p+1,2q+1}$. Then $d(G) = 2^n -1 + 2[a(G)-b(G)]$. We also
show some new relations between the domination polynomial and the neighborhood
polynomial of a graph.