Minimum Coverage by Dominating Sets in Graphs

Abstract

The $[0,\mathrm{\infty })$-valued dominating function minimization problem has the $[0,\mathrm{\infty })$-valued packing function as its linear programming dual. The standard $\{0,1\}$-valued minimum dominating set problem has the $\{0,1\}$-valued maximum packing set problem as its binary dual. The recently introduced complementary problem to a minimization problem is also a maximization problem, and the complementary problem to domination is the maximum enclaveless problem. This paper investigates the dual of the enclaveless problem, namely, the domination-coverage number of a graph. Specifically, let $\eta (G)$ denote the minimum total coverage of a dominating set. The number of edges covered by a vertex $v$ equals its degree, $\mathrm{deg}v$, so $\eta (G)=\text{MIN}\{\sum _{s\in S}\mathrm{deg}s:S\text{ is a dominating set}\}$. Bounds on $\eta (G)$ and computational complexity results are presented.