Computing the k-metric dimension of graphs

Identifier:  imarina:9295801

Handle: https://hdl.handle.net/20.500.11797/imarina9295801

Authors:  Yero, IG; Estrada-Moreno, A; Rodríguez-Velázquez, JA

Abstract:
Given a connected graph G = (V, E), a set S subset of V is a k-metric generator for G if for any two different vertices u, v is an element of V, there exist at least k vertices w(1), ... ,W-k is an element of S such that d(G)(u, w(i)) not equal d(G) (v, w(i)) for every i is an element of {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. (C) 2016 Elsevier Inc. All rights reserved.