Menu
The \([0,\infty)\)-valued dominating function minimization problem has the \([0,\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, \(\deg v\), so \(\eta(G) = \text{MIN}\{\sum_{s \in S} \deg s: S \text{ is a dominating set}\}\). Bounds on \(\eta(G)\) and computational complexity results are presented.