The k-metric dimension of a graph: Complexity and algorithms
Ismael G. Yero, Alejandro Estrada‐Moreno · arXiv (Cornell University) · 2014
Given a connected graph G = (V,E), a set S ⊆ V is said to be a k-metric generator for G if the elements of any pair of vertices of G are distinguished by at least k elements of S, i.e., for any two different vertices u,v ∈ V , there exist at least k vertices w1,w2,...,wk ∈ S such that dG(u,wi) 6 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 show that the problem of computing the k-metric dimension of graphs is NP-Complete. However, the problem is solved in linear time for the particular case of trees. A connected graph G is k-metric dimensional if k is the largest integer such that there exists a k-metric basis for G. We also show that the problem of finding the integer k such that a graph G is k-metric dimensional can be solved in polynomial time.