Movable Dominating Sensor Sets in Networks

Abstract

In this paper we consider 1-movable dominating sets, motivated by the use of sensors employed to detect certain events in networks, where the sensors have a limited ability to react under changing conditions in the network. A 1-movable dominating set is a dominating set $S\subseteq V(G)$ such that for every $v\in S$, either $S–\{v\}$ is a dominating set, or there exists a vertex $u\in (V(G)–S)\cap N(v)$ such that $(S–\{v\})\cup \{u\}$ is a dominating set. We present computational complexity results and bounds on the size of 1-movable dominating sets in arbitrary graphs. We also give a polynomial time algorithm to find minimum 1-movable dominating sets for trees. We conclude by extending this idea to $k$-movable dominating sets.