On the Metric Dimension of Möbius Ladders

Abstract

If \(G\) is a connected graph, the distance \(d(u, v)\) between two vertices \(u,v \in V(G)\) is the length of a shortest path between them. Let \(W = \{w_1, w_2, \ldots, w_k\}\) be an ordered set of vertices of \(G\) and let \(v\) be a vertex of \(G\). The representation \(r(v|W)\) of \(v\) with respect to \(W\) is the \(k\)-tuple \((d(v, w_1), d(v, w_2), \ldots, d(v, w_k))\). If distinct vertices of \(G\) have distinct representations with respect to \(W\), then \(W\) is called a resolving set or locating set for \(G\). A resolving set of minimum cardinality is called a basis for \(G\) and this cardinality is the metric dimension of \(G\), denoted by \(\dim(G)\).

A family \(\mathcal{G}\) of connected graphs is a family with constant metric dimension if \(\dim(G)\) does not depend upon the choice of \(G\) in \(\mathcal{G}\). In this paper, we are dealing with the study of metric dimension of Möbius ladders. We prove that Möbius ladder \(M_n\) constitute a family of cubic graphs with constant metric dimension and only three vertices suffice to resolve all the vertices of Möbius ladder \(M_n\), except when \(n \equiv 2 \pmod{8}\). It is natural to ask for the characterization of regular graphs with constant metric dimension.