Optimal $(t,r)$ Broadcasts On the Infinite Grid

Abstract

Let $G=(V,E)$ be a graph and $t,r$ be positive integers. The signal that a vertex $v$ receives from a tower of signal strength $t$ located at vertex $T$ is defined as $sig(v,T)=max(t-dist(v,T),0)$, where $dist(v,T)$ denotes the distance between the vertices $v$ and $T$. In 2015 Blessing, Insko, Johnson, and Mauretour defined a $(t,r)$ broadcast dominating set, or simply a $(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$ is at least $r$. We say that $\mathbb{T}$ is optimal if $|\mathbb{T}|$ is minimal among all such sets $\mathbb{T}$. The cardinality of an optimal $(t,r)$ broadcast on a finite graph $G$ is called the $(t,r)$ broadcast domination number of $G$. The concept of $(t,r)$ broadcast domination generalizes the classical problem of domination on graphs. In fact, the $(2,1)$ broadcasts on a graph $G$ are exactly the dominating sets of $G$. In their paper, Blessing et al. considered $(t,r)\in \{(2,2),(3,1),(3,2),(3,3)\}$ and gave optimal $(t,r)$ broadcasts on $G_{m,n}$, the grid graph of dimension $m\times n$, for small values of $m$ and $n$. They also provided upper bounds on the optimal $(t,r)$ broadcast numbers for grid graphs of arbitrary dimensions. In this paper, we define the density of a $(t,r)$ broadcast, which allows us to provide optimal $(t,r)$ broadcasts on the infinite grid graph for all $t\ge 2$ and $r=1,2$, and bound the density of the optimal $(t,3)$ broadcast for all $t\ge 2$. In addition, we give a family of counterexamples to the conjecture of Blessing et al. that the optimal $(t,r)$ and $(t+1,r+2)$ broadcasts are identical for all $t\ge 1$ and $r\ge 1$ on the infinite grid.

17 pages, 16 figures, 1 table

References in corpus (1)

• Distributed Dominating Sets on Grids