Movable Dominating Sensor Sets in Networks

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.