Distance-k locating-dominating sets in graphs

zbMATH Open1492.05117arXiv2106.14848MaRDI QIDQ5087673FDOQ5087673

Publication date: 1 July 2022

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.

Full work available at URL: https://arxiv.org/abs/2106.14848

Recommendations

zbMATH Keywords

domination number metric dimension locating-dominating set \((s,t)\)-locating-dominating set distance-\(k\) locating-dominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Cited In (8)

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)