Computing upper bounds for optimal density of $(t,r)$ broadcasts on the infinite grid

• DOI: 10.48550/arxiv.1712.00150
• Publication Date: 2017-01-01
• Authors: Drews, Benjamin F.; Harris, Pamela E.; Randolph, Timothy W.
• Keywords: FOS: Mathematics; Mathematics - Combinatorics; 05C69, 05C12, 0530, 68R05, 68R10; 0102 computer and information sciences; Combinatorics (math.CO); 01 natural sciences

The domination number of a finite graph $G$ with vertex set $V$ is the cardinality of the smallest set $S\subseteq V$ such that for every vertex $v\in V$ either $v\in S$ or $v$ is adjacent to a vertex in $S$. A set $S$ satisfying these conditions is called a dominating set. In 2015 Blessing, Insko, Johnson, and Mauretour introduced $(t,r)$ broadcast domination, a generalization of graph domination parameterized by the nonnegative integers $t$ and $r$. In this setting, we say that the signal a vertex $v\in V$ receives from a tower of strength $t$ located at vertex $T$ is defined by $sig(v,T)=max(t-dist(v,T),0)$. Then a $(t,r)$ broadcast dominating set on $G$ is a set $S\subseteq V$ such that the sum of all signal received at each vertex $v \in V$ is at least $r$. In this paper, we consider $(t,r)$ broadcasts of the infinite grid and present a Python program to compute upper bounds on the minimal density of a $(t,r)$ broadcast on the infinite grid. These upper bounds allow us to construct counterexamples to a conjecture by Blessing et al. that the $(t,r)$ and $(t+1, r+2)$ broadcasts are equal whenever $t,r\geq 1$.<br/>7 pages, 2 figures, 1 table<br/>