On \((t, r)\) broadcast domination of certain grid graphs (Q6148305)

A generalization of the concept of domination in graphs is \((t, r )\) broadcast domination, which can defined as follows: certain vertices of a graph \(G\) are designated to be towers of signal strength \(t\), which send out signal to neighboring vertices with signal strength decaying linearly as the signal traverses the edges of the graph. Let \(\mathbb{T}\) be the set of all towers, and define the signal received by a vertex \(v \in V(G)\) from all towers \(w \in \mathbb{ T}\) to be \(f (v) =\sum_{w\in \mathbb{T}}\max(0,t-d(v,w))\). \textit{D. Blessing} et al. [Discrete Appl. Math. 187, 19--40 (2015; Zbl 1315.05098)] defined a \((t, r )\) broadcast dominating set, or a \((t, r )\) broadcast, on \(G\) as a set \(\mathbb{T} \subseteq V(G)\) such that \(f(v) \geq r\) for all \(v \in V(G)\). The minimum cardinality of a \((t, r )\) broadcast on \(G\) is called the \((t, r )\) broadcast domination number of \(G\). In this paper, the authors present some evaluations on the \((t, r )\) broadcast domination number for certain graphs including paths, grid graphs, the slant lattice, and the king's lattice. For example, the \((t, r )\) broadcast domination number of the king's grid graph with \(m\) rows and \(n\) columns equals \(\lceil (n+r-1)/(2t-r) \rceil\) for \(t > r\) and \(m \leq 2(t -r )+1\).