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

MaRDI QIDQ6294672zbMATH OpenFDO

Authors Benjamin F. Drews, Pamela E. Harris, Timothy W. Randolph

Publication date 30 November 2017

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Abstract: The domination number of a finite graph $G$ with vertex set $V$ is the cardinality of the smallest set $SsubseteqV$ such that for every vertex $vinV$ either $vinS$ 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 $vinV$ 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 $SsubseteqV$ such that the sum of all signal received at each vertex $vinV$ 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,rgeq1$.

This page was built for publication: Computing upper bounds for optimal density of $(t,r)$ broadcasts on the infinite grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6294672)