On two families of graphs with constant metric dimension

Abstract

If GG is a connected graph, the distance d(u, v) between two vertices u,v∈V(G)u,v∈V(G) is the length of a shortest path between them. Let W=w1,w2,….,wkW=w1,w2,….,wk be an ordered set of vertices of GG and let vv be a vertex of GG. The representation r(v|W) of vv with respect to WW is the k-tuple (d(v,w1),d(v,w2),…..,d(v,wk))(d(v,w1),d(v,w2),…..,d(v,wk)). If distinct vertices of GG have distinct representations with respect to W, then W is called a resolving set or locating set for GG. A resolving set of minimum cardinality is called a basis for GG and this cardinality is the metric dimension of GG, denoted by dim(G)dim(G). A family G of connected graphs is a family with constant metric dimension if dim(G)dim(G) does not depend upon the choice of GG in GG. In this paper, we show that the graphs (D^{∗}_{p}\) and DnpDpn, obtained from prism graph have constant metric dimension.