On the complexity of computing the k-metric dimension of graphs

Original · EN

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 w₁,...,wₖ∈ S such that dG(u,wᵢ)≠ dG(v,wᵢ) 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 study some problems regarding 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-Complete. However, the problem is solved in linear time for the particular case of trees.