Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6420693 | Applied Mathematics and Computation | 2015 | 8 Pages |
â¢A new concept resolving-power dominating sets is introduced.â¢The problem is proven to be NP-complete.â¢The resolving power domination number is studied for trees.
For a graph G(V,E) that models a facility or a multi-processor network, detection devices can be placed at vertices so as to identify the location of an intruder such as a thief or fire or saboteur or a faulty processor. Resolving-power dominating sets are of interest in electric networks when the latter helps in the detection of an intruder/fault at a vertex. We define a set SâV to be a resolving-power dominating set of G if it is resolving as well as a power-dominating set. The minimum cardinality of S is called resolving-power domination number. In this paper, we show that the problem is NP-complete for arbitrary graphs and that it remains NP-complete even when restricted to bipartite graphs. We provide lower bounds for the resolving-power domination number for trees and identify classes of trees that attain the lower bound. We also solve the problem for complete binary trees.