Distance-k locating-dominating sets in graphs

Abstract: Let

G

be a graph with vertex set

V

, and let

k

be a positive integer. A set

D s u b s e t e q V

is a emph{distance-

k

dominating set} of

G

if, for each vertex

u i n V - D

, there exists a vertex

w i n D

such that

d (u, w) l e k

, where

d (u, w)

is the minimum number of edges linking

u

and

w

in

G

. Let

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

. A set

R s u b s e t e q V

is a emph{distance-

k

resolving set} of

G

if, for any pair of distinct

x, y i n V

, there exists a vertex

z i n R

such that

d_{k} (x, z) e q d_{k} (y, z)

. The emph{distance-

k

domination number}

g a m m a_{k} (G)

(emph{distance-

k

dimension}

d i m_{k} (G)

, respectively) of

G

is the minimum cardinality of all distance-

k

dominating sets (distance-

k

resolving sets, respectively) of

G

. The emph{distance-

k

location-domination number},

g a m m a_{L}^{k} (G)

, of

G

is the minimum cardinality of all sets

S s u b s e t e q V

such that

S

is both a distance-

k

dominating set and a distance-

k

resolving set of

G

. Note that

g a m m a_{L}^{1} (G)

is the well-known location-domination number introduced by Slater in 1988. For any connected graph

G

of order

n g e 2

, we obtain the following sharp bounds: (1)

g a m m a_{k} (G) l e d i m_{k} (G) + 1

; (2)

2 l e g a m m a_{k} (G) + d i m_{k} (G) l e n

; (3)

1 l e m a x g a m m a_{k} (G), d i m_{k} (G) l e g a m m a_{L}^{k} (G) l e m i n d i m_{k} (G) + 1, n - 1

. We characterize

G

for which

g a m m a_{L}^{k} (G) i n 1, | V | - 1

. We observe that

f r a c d i m_{k} (G) g a m m a_{k} (G)

can be arbitrarily large. Moreover, for any tree

T

of order

n g e 2

, we show that

g a m m a_{L}^{k} (T) l e n - e x (T)

, where

e x (T)

denotes the number of exterior major vertices of

T

, and we characterize trees

T

achieving equality. We also examine the effect of edge deletion on the distance-

k

location-domination number of graphs.

Recommendations

Cited in

(9)

This page was built for publication: Distance-\(k\) locating-dominating sets in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5087673)