Tight Bounds for (t,2) Broadcast Domination on Finite Grids. (arXiv:1805.06058v1 [math.CO])

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 signal 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. esta 查看全文>>