The metric dimension of the lexicographic product of graphs

Abstract

For a set W of vertices and a vertex v in a connected graph G, the k-vector rW(v)=(d(v,w1),⋯,d(v,wk)) is the metric representation of v with respect to W, where W=w1,⋯,wk and d(x,y) is the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct metric representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension. In this paper, we study the metric dimension of the lexicographic product of graphs G and H, denoted by G[H]. First, we introduce a new parameter, the adjacency dimension, of a graph. Then we obtain the metric dimension of G[H] in terms of the order of G and the adjacency dimension of H. © 2012 Elsevier B.V. All rights reserved.