Details

Autor(en) / Beteiligte

• Schmitz, Yannick
• Vietz, Duygu
• Wanke, Egon

Titel

A note on the complexity of k-metric dimension

Ist Teil von

• Applied mathematics and computation, 2023-11, Vol.457, p.128204, Article 128204

Ort / Verlag

Elsevier Inc

Erscheinungsjahr

2023

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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].