Characterization of randomly k-dimensional graphs.

Abstract: For an ordered set

W = w_{1}, w_{2}, ..., 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}), ., 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 complete graph

K_{k + 1}

or an odd cycle.

Recommendations

Cited in

(3)

This page was built for publication: Characterization of randomly \(k\)-dimensional graphs.