Computing the k-metric dimension of graphs

摘要

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.