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

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 $sig(T,v)=max(t-dist(T,v),0),$ where $dist(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 $\mathbb{T}\subseteq V$ such that the sum of all signals received at each vertex $v\in V$ from the set of towers $\mathbb{T}$ is at least $r$. The $(t,r)$ broadcast domination number of a finite graph $G$, denoted ${\gamma }_{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\times n$ grid graph $G_{m,n}$. In 2014, Grez and Farina bounded the $k$-distance domination number for grid graphs, equivalent to bounding ${\gamma }_{t,1}(G_{m,n})$. In 2015, Blessing et al. established bounds on ${\gamma }_{2,2}(G_{m,n})$, ${\gamma }_{3,2}(G_{m,n})$, and ${\gamma }_{3,3}(G_{m,n})$. In this paper, we take the next step and provide a tight upper bound on ${\gamma }_{t,2}(G_{m,n})$ for all $t>2$. We also prove the conjecture of Blessing et al. that their bound on ${\gamma }_{3,2}(G_{m,n})$ is tight for large values of $m$ and $n$.

8 pages, 4 figures

References in corpus (1)

• The Domination Number of Grids

Cited by in corpus (1)

• (t,r) broadcast domination in the infinite grid