On the metric dimension of circulant and Harary graphs

摘要

A metric generator is a set W of vertices of a graph G(V,E) such that for every pair of vertices u,v of G, there exists a vertex w∈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.