Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids

Publication date: 10 October 2019

Abstract: Let

G = (V, E)

be a graph and

t, r

be positive integers. The emph{signal} that a tower vertex

T

of signal strength

t

supplies to a vertex

v

is defined as

s i g (T, v) = m a x (t - d i s t (T, v), 0),

where

d i s t (T, v)

denotes the distance between the vertices

v

and

T

. In 2015 Blessing, Insko, Johnson, and Mauretour defined a emph{

(t, r)

broadcast dominating set}, or simply a emph{

(t, r)

broadcast}, on

G

as a set

m a t h b b T s u b s e t e q V

such that the sum of all signals received at each vertex

v i n V

from the set of towers

m a t h b b T

is at least

r

. The

(t, r)

broadcast domination number of a finite graph

G

, denoted

g a m m a_{t, r} (G)

, is the minimum cardinality over all

(t, r)

broadcasts for

G

. Recent research has focused on bounding the

(t, r)

broadcast domination number for the

m i m e s n

grid graph

G_{m, n}

. In 2014, Grez and Farina bounded the

k

-distance domination number for grid graphs, equivalent to bounding

g a m m a_{t, 1} (G_{m, n})

. In 2015, Blessing et al. established bounds on

g a m m a_{2, 2} (G_{m, n})

,

g a m m a_{3, 2} (G_{m, n})

, and

g a m m a_{3, 3} (G_{m, n})

. In this paper, we take the next step and provide a tight upper bound on

g a m m a_{t, 2} (G_{m, n})

for all

t > 2

. We also prove the conjecture of Blessing et al. that their bound on

g a m m a_{3, 2} (G_{m, n})

is tight for large values of

m

and

n

.

Cited In (4)

   Recommendations

This page was built for publication: Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids