The k-metric dimension of the lexicographic product of graphs

摘要

Given a simple and connected graph G = (V, E), and a positive integer k, a set S subset of V is said to be a k-metric generator for G, if for any pair of different vertices u, v epsilon V, there exist at least k vertices w(1), w(2), ..., w(k) epsilon S such that d(G)(u, w(i)) not equal d(G)(v, wi), for every i epsilon {1, ... k}, where d(G)(x, y) denotes the distance between x and y. The minimum cardinality of a k-metric generator is the k-metric dimension of G. A set S subset of V is a k-adjacency generator for G if any two different vertices x, y epsilon V(G) satisfy vertical bar((N-G(x) del N-G(y)) boolean OR {x, y}) boolean AND S vertical bar >= k, where N-G(x) del N-G(.y) is the symmetric difference of the neighborhoods of x and y. The minimum cardinality of any k-adjacency generator is the k-adjacency dimension of G. In this article we obtain tight bounds and closed formulae for the k-metric dimension of the lexicographic product of graphs in terms of the k-adjacency dimension of the factor graphs. (C) 2016 Elsevier B.V. All rights reserved.