- Title
- Resolving-power dominating sets
- Creator
- Stephen, Sudeep; Rajan, Bharati; Grigorious, Cyriac; William, Albert
- Relation
- Applied Mathematics and Computation Vol. 256, p. 778-785
- Publisher Link
- http://dx.doi.org/10.1016/j.amc.2015.01.037
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2015
- Description
- 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.
- Subject
- domination; power domination; metric domination
- Identifier
- http://hdl.handle.net/1959.13/1336435
- Identifier
- uon:27616
- Identifier
- ISSN:0096-3003
- Language
- eng
- Reviewed
- Hits: 911
- Visitors: 965
- Downloads: 1
Thumbnail | File | Description | Size | Format |
---|