On (t, r) broadcast domination of certain grid graphs

Abstract: Let

G = (V (G), E (G))

be a connected graph with vertex set

V (G)

and edge set

E (G)

. We say a subset

D

of

V (G)

dominates

G

if every vertex in

V s e t m i n u s D

is adjacent to a vertex in

D

. A generalization of this concept is

(t, r)

broadcast domination. We designate certain vertices to be towers of signal strength

t

, which send out signal to neighboring vertices with signal strength decaying linearly as the signal traverses the edges of the graph. We let

m a t h b b T

be the set of all towers, and we define the signal received by a vertex

v i n V (G)

from a tower

w i n m a t h b b T

to be

f (v) = s u m_{w i n m a t h b b T} m a x (0, t - d (v, w))

. Blessing, Insko, Johnson, Mauretour (2014) defined a

(t, r)

broadcast dominating set, or a

(t, r)

broadcast, on

G

as a set

m a t h b b T s u b s e t e q V (G)

such that

f (v) g e q r

for all

v i n V (G)

. The minimal cardinality of a

(t, r)

broadcast on

G

is called the

(t, r)

broadcast domination number of

G

. In this paper, we present our research on the

(t, r)

broadcast domination number for certain graphs including paths, grid graphs, the slant lattice, and the king's lattice.

Recommendations

Cites work

This page was built for publication: On \((t, r)\) broadcast domination of certain grid graphs