Metric-locating-dominating sets of graphs for constructing related subsets of vertices

Antonio González, Carmen Hernando and Mercè Mora

Applied Mathematics and Computation, 2018, vol. 332, issue C, 449-456

Abstract: A dominating set S of a graph is a metric-locating-dominating set if each vertex of the graph is uniquely distinguished by its distances from the elements of S, and the minimum cardinality of such a set is called the metric-location-domination number. In this paper, we undertake a study that, in general graphs and specific families, relates metric-locating-dominating sets to other special sets: resolving sets, dominating sets, locating-dominating sets and doubly resolving sets. We first characterize the extremal trees of the bounds that naturally involve metric-location-domination number, metric dimension and domination number. Then, we prove that there is no polynomial upper bound on the location-domination number in terms of the metric-location-domination number, thus extending a result of Henning and Oellermann. Finally, we show different methods to transform metric-locating-dominating sets into locating-dominating sets and doubly resolving sets. Our methods produce new bounds on the minimum cardinalities of all those sets, some of them concerning parameters that have not been related so far.

Keywords: Metric-locating-dominating set; Resolving set; Dominating set; Locating-dominating set; Doubly resolving set (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318302261
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:332:y:2018:i:c:p:449-456

DOI: 10.1016/j.amc.2018.03.053

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().