# zbMATH — the first resource for mathematics

Families of regular graphs with constant metric dimension. (English) Zbl 1178.05037
Summary: 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_1,\dots,w_k\}$$ is called a resolving set for $$G$$ if for every two distinct vertices $$x, y\in V(G)$$, there is a vertex $$w_i\in W$$ such that $$d(x,w_i)\neq 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 $$\mathcal G$$ 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 $$\mathcal G$$. In this paper, we show that generalized Petersen graphs $$P(n,2)$$, antiprisms $$A_n$$ and Harary graphs $$H_{4,n}$$ for $$n\not\equiv 1\pmod 4$$ are families of regular graphs with constant metric dimension and raise some questions in a more general setting.

##### MSC:
 05C12 Distance in graphs