.png){kind=icon}
.png){kind=icon}
Return
Resolving-power dominating sets
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2015.01.037.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 subset of 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. (C) 2015 Elsevier Inc. All rights reserved.
Keywords:
Domination
Power domination
Metric dimension
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W