Counting Dominating Sets of Graphs

MaRDI QIDQ6281862zbMATH OpenFDO

Authors Irene Heinrich, Peter Tittmann

Publication date 12 January 2017

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.

This page was built for publication: Counting Dominating Sets of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281862)