The distance-k dimension of graphs

Abstract: The metric dimension,

d i m (G)

, of a graph

G

is a graph parameter motivated by robot navigation that has been studied extensively. Let

G

be a graph with vertex set

V (G)

, and let

d (x, y)

denote the length of a shortest

x - y

path in

G

. For a positive integer

k

and for distinct

x, y i n V (G)

, let

d_{k} (x, y) = m i n d (x, y), k + 1

and let

R_{k} x, y = z i n V (G) : d_{k} (x, z) e q d_{k} (y, z)

. A subset

S s u b s e t e q V (G)

is a distance-

k

resolving set of

G

if

| S c a p R_{k} x, y | g e 1

for any pair of distinct

x, y i n V (G)

, and the distance-

k

dimension,

d i m_{k} (G)

, of

G

is the minimum cardinality over all distance-

k

resolving sets of

G

. In this paper, we study the distance-

k

dimension of graphs. We obtain some general bounds for distance-

k

dimension. For all

k g e 1

, we characterize connected graphs

G

of order

n

with

d i m_{k} (G) g e n - 2

. We determine

d i m_{k} (G)

when

G

is a cycle or a path. We also examine the effect of vertex or edge deletion on the distance-

k

dimension of graphs.

This page was built for publication: The distance-k dimension of graphs