(t,r) broadcast domination in the infinite grid

Abstract

The $(t,r)$ broadcast domination number of a graph $G$, ${\gamma }_{t,r}(G)$, is a generalization of the domination number of a graph. ${\gamma }_{t,r}(G)$ is the minimal number of towers needed, placed on vertices of $G$, each transmitting a signal of strength $t$ which decays linearly, such that every vertex receives a total amount of at least $r$ signal. In this paper we prove a conjecture by Drews, Harris, and Randolph about the minimal density of towers in ${\mathbb{Z}}^2$ that provide a $(t,3)$ domination broadcast for $t>17$ and explore generalizations. Additionally, we determine the $(t,r)$ broadcast domination number of powers of paths, $P_n^{(k)}$ and powers of cycles, $C_n^{(k)}$.

12 pages, 6 figures