Capacitated Domination

Abstract

We define an \(r\)-capacitated dominating set of a graph \(G = (V,E)\) as a set \(\{v_1, \ldots, v_k\} \subseteq V\) such that there is a partition \((V_1, \ldots, V_k)\) of \(V\) where for all \(i\), \( v_i \in V_i\), \(v_i\) is adjacent to all of \(V_i – \{v_i\}\), and \(|V_i| \leq r + 1\). \(\daleth_r(G)\) is the minimum cardinality of an \(r\)-capacitated dominating set. We show properties of \(\daleth_r\), especially as regards the trivial lower bound \(|V|/(r + 1)\). We calculate the value of the parameter in several graph families, and show that it is related to codes and polyominoes. The parameter is \(NP\)-complete in general to compute, but a greedy approach provides a linear-time algorithm for trees.