Characterization of Randomly \(k\)-Dimensional Graphs

Abstract

For an ordered set \(W = \{w_1, w_2, \ldots, w_k\}\) of vertices and a vertex \(v\) in a connected graph \(G\), the ordered \(k\)-vector \(r(v|W) := (d(v, w_1), d(v, w_2), \ldots, d(v, w_k))\) is called the (metric) representation of \(v\) with respect to \(W\), where \(d(x, y)\) is the distance between the vertices \(x\) and \(y\). The set \(W\) is called a resolving set for \(G\) if distinct vertices of \(G\) have distinct representations with respect to \(W\). A minimum resolving set for \(G\) is a basis of \(G\) and its cardinality is the metric dimension of \(G\). The resolving number of a connected graph \(G\) is the minimum \(k\) such that every \(k\)-set of vertices of \(G\) is a resolving set. A connected graph \(G\) is called randomly \(k\)-dimensional if each \(k\)-set of vertices of \(G\) is a basis. In this paper, along with some properties of randomly \(k\)-dimensional graphs, we prove that a connected graph \(G\) with at least two vertices is randomly \(k\)-dimensional if and only if \(G\) is a complete graph \(K_{k+1}\) or an odd cycle.