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’\) of \(G\), then \(D’\) is called an inverse dominating set of \(G\) with respect to \(D\). The inverse domination number \(\gamma'(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'(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.