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

• DOI: 10.48550/arxiv.1805.06058
• Publication Date: 2018-01-01
• Authors: Randolph, Timothy W
• Keywords: Broadcasts; Grid Graphs; FOS: Mathematics; Discrete Mathematics and Combinatorics; Mathematics - Combinatorics; 0102 computer and information sciences; Combinatorics (math.CO); Domination; 01 natural sciences

8 pages, 4 figures<br/>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 $��_{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 $��_{t,1}(G_{m,n})$. In 2015, Blessing et al. established bounds on $��_{2,2}(G_{m,n})$, $��_{3,2}(G_{m,n})$, and $��_{3,3}(G_{m,n})$. In this paper, we take the next step and provide a tight upper bound on $��_{t,2}(G_{m,n})$ for all $t>2$. We also prove the conjecture of Blessing et al. that their bound on $��_{3,2}(G_{m,n})$ is tight for large values of $m$ and $n$.<br/>