Movable Dominating Sensor Sets in Networks
Jean R. S. Blair, Ralucca Gera, Steve Horton · 2011
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 con-ditions in the network. A 1-movable dominating set is a dominating set S ⊆ V (G) such that for every v ∈ S, either S − {v} is a dom-inating set, or there exists a vertex u ∈ (V (G) − S) ∩ N(v) such that (S − {v}) ∪ {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.