A note on the complexity of k-metric dimension

Yannick Schmitz, Duygu Vietz and Egon Wanke

Applied Mathematics and Computation, 2023, vol. 457, issue C

Abstract: Two vertices u,v∈V of an undirected connected graph G=(V,E) are resolved by a vertex w if the distance between u and w and the distance between v and w are different. A set R⊆V of vertices is a k-resolving set for G if for each pair of vertices u,v∈V there are at least k distinct vertices w1,…,wk∈R such that each of them resolves u and v. The k-Metric Dimension of G is equal to the size of a smallest k-resolving set for G. The decision problem k-Metric Dimension is the question whether G has a k-resolving set of size at most r, for a given graph G and a given number r. In this paper, we proof the NP-completeness of k-Metric Dimension for bipartite graphs and each k≥2, which corrects the proof in [1].

Keywords: Metric dimension; K-Metric dimension; Resolving set; Metric generator (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323003739
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:457:y:2023:i:c:s0096300323003739

DOI: 10.1016/j.amc.2023.128204

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