The metric dimension of the lexicographic product of graphs

For a set WW of vertices and a vertex vv in a connected graph GG, the kk-vector rW(v)=(d(v,w1),…,d(v,wk))rW(v)=(d(v,w1),…,d(v,wk)) is the metric representation   of vv with respect to WW, where W={w1,…,wk}W={w1,…,wk} and d(x,y)d(x,y) is the distance between the vertices xx and yy. The set WW is a resolving set   for GG if distinct vertices of GG have distinct metric representations with respect to WW. The minimum cardinality of a resolving set for GG is its metric dimension  . In this paper, we study the metric dimension of the lexicographic product of graphs GG and HH, denoted by G[H]G[H]. First, we introduce a new parameter, the adjacency dimension  , of a graph. Then we obtain the metric dimension of G[H]G[H] in terms of the order of GG and the adjacency dimension of HH.