2011/03/18 by Jannesari, Mohsen, Omoomi, Behnaz
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1103.3570
For an ordered set W=\w1,w2,...,wk\ of vertices and a vertex v in a connected graph G, the ordered k-vector r(v|W):=(d(v,w1),d(v,w2),.,d(v,wk)) 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 complete graph Kk+1 or an odd cycle.