The Inverse Domination Number of a Graph

Abstract

Let $G$ be a graph with $n$ vertices and let $D$ be a minimum dominating set of $G$. If $V–D$ contains a dominating set $D^{\prime }$ of $G$, then $D^{\prime }$ is called an inverse dominating set of $G$ with respect to $D$. The inverse domination number ${\gamma }^{\prime }(G)$ of $G$ is the cardinality of a smallest inverse dominating set of $G$. In this paper, we characterise graphs for which $\gamma (G)+{\gamma }^{\prime }(G)=n$. We give a lower bound for the inverse domination number of a tree and give a constructive characterisation of those trees which achieve this lower bound.