Resolving-power dominating sets
Journal article
Stephen, Sudeep, Rajan, Bharati, Grigorious, Cyriac and William, Albert. (2015). Resolving-power dominating sets. Applied Mathematics and Computation. 256, pp. 778-785. https://doi.org/10.1016/j.amc.2015.01.037
Authors | Stephen, Sudeep, Rajan, Bharati, Grigorious, Cyriac and William, Albert |
---|---|
Abstract | 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. |
Keywords | Domination; Power domination; Metric dimension |
Year | 01 Jan 2015 |
Journal | Applied Mathematics and Computation |
Journal citation | 256, pp. 778-785 |
Publisher | Academic Press (Elsevier) |
ISSN | 0096-3003 |
Digital Object Identifier (DOI) | https://doi.org/10.1016/j.amc.2015.01.037 |
Web address (URL) | https://www.sciencedirect.com/science/article/pii/S009630031500051X?via%3Dihub |
Research or scholarly | Research |
Page range | 778-785 |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
01 Apr 2015 | |
Online | 15 Feb 2015 |
Publication process dates | |
Deposited | 22 May 2024 |
Additional information | © 2015 Elsevier Inc. All rights reserved. |
Place of publication | United States |
https://acuresearchbank.acu.edu.au/item/907v9/resolving-power-dominating-sets
Restricted files
Publisher's version
32
total views0
total downloads16
views this month0
downloads this month