Characterization of randomly k-dimensional graphs

Abstract

For an ordered set W = {ω1, ω1,···, ωk} of vertices and a vertex v in a connected graph G, the ordered fc-vector r(ν|W):= (d(ν, ω1), d(ν, ω1),···, d{ν, ω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 fc-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 fc-dimensional if and only if G is complete graph Kk+1 or an odd cycle.