The metric dimension of the lexicographic product of graphs

A set of vertices WWresolves   a graph GG if every vertex is uniquely determined by its coordinate of distances to the vertices in WW. The minimum cardinality of a resolving set of GG is called the metric dimension   of GG. In this paper, we consider a graph which is obtained by the lexicographic product between two graphs. The lexicographic product   of graphs GG and HH, which is denoted by G∘HG∘H, is the graph with vertex set V(G)×V(H)={(a,v)|a∈V(G),v∈V(H)}V(G)×V(H)={(a,v)|a∈V(G),v∈V(H)}, where (a,v)(a,v) is adjacent to (b,w)(b,w) whenever ab∈E(G)ab∈E(G), or a=ba=b and vw∈E(H)vw∈E(H). We give the general bounds of the metric dimension of a lexicographic product of any connected graph GG and an arbitrary graph HH. We also show that the bounds are sharp.