Capacitated Domination

Abstract

We define an $r$-capacitated dominating set of a graph $G=(V,E)$ as a set $\{v_1,\dots ,v_k\}\subseteq V$ such that there is a partition $(V_1,\dots ,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|\le 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.