Families of regular graphs with constant metric dimension

Abstract

Let G be a connected graph and d(x, y) be the distance between the vertices x and y. A subset of vertices W = {w₁,. . . ,W_k} is called a resolving set for G if for every two distinct vertices x, y ε V(G), there is a vertex w_i ε W such that d(x,W_i) ≠ d(y, w_i). A resolving set containing a minimum number of vertices is called a metric basis for G and the number of vertices in a metric basis is its metric dimension dim(G). A family of connected graphs Q is said to be a family with constant metric dimension if dim(G) is finite and does not depend upon the choice of G in g. In this paper, we show that generalized Petersen graphs P(n, 2), antiprisms A_n and Harary graphs H_4,n for n ≢ 1(mod 4) are families of regular graphs with constant metric dimension and raise some questions in a more general setting.