On the metric dimension of circulant and Harary graphs

A metric generator is a set W   of vertices of a graph G(V,E)G(V,E) such that for every pair of vertices u,vu,v of G  , there exists a vertex w∈Ww∈W with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. In this case the vertex w is said to resolve or distinguish the vertices u and v. The minimum cardinality of a metric generator for G is called the metric dimension. The metric dimension problem is to find a minimum metric generator in a graph G  . In this paper, we make a significant advance on the metric dimension problem for circulant graphs C(n,±{1,2,…,j}),1⩽j⩽⌊n/2⌋,n⩾3, and for Harary graphs.