Computing the k-metric dimension of graphs

Ismael G. Yero, Alejandro Estrada-Moreno and Juan A. Rodríguez-Velázquez

Applied Mathematics and Computation, 2017, vol. 300, issue C, 60-69

Abstract: Given a connected graph G=(V,E), a set S ⊆ V is a k-metric generator for G if for any two different vertices u, v ∈ V, there exist at least k vertices w1,…,wk∈S such that dG(u, wi) ≠ dG(v, wi) for every i∈{1,…,k}. A metric generator of minimum cardinality is called a k-metric basis and its cardinality the k-metric dimension of G. We make a study concerning the complexity of some k-metric dimension problems. For instance, we show that the problem of computing the k-metric dimension of graphs is NP-hard. However, the problem is solved in linear time for the particular case of trees.

Keywords: k-metric dimension; k-metric dimensional graph; Metric dimension; NP-complete problem; NP-hard problem; Graph algorithms (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300316307317
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:300:y:2017:i:c:p:60-69

DOI: 10.1016/j.amc.2016.12.005

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 ().