Families of regular graphs with constant metric dimension. (English) Zbl 1178.05037

Javaid, Imran; Tariq Rahim, M.; Ali, Kashif

Util. Math. 75, 21-33 (2008).

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

Keywords:

metric dimension; metric basis; resolving set; generalized Petersen graph; antiprism; Harary graph