2017/11/29 by Benjamin F. Drews, Pamela E. Harris, Drews, Benjamin F. +3 · 1 citation
Computer Science · #0530 #05C12 #05C69 #68R05 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1711.11116
openalex publication_date 2017/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \mathbbT⊆ V such that the sum of all signal received at each vertex v ∈ V is at least r. We say that \mathbbT is optimal if |\mathbbT| is minimal among all such sets \mathbbT. 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)∈\(2,2),(3,1),(3,2),(3,3)\ and gave optimal (t,r) broadcasts on Gm,n, the grid graph of dimension m× 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≥2 and r=1,2, and bound the density of the optimal (t,3) broadcast for all t≥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≥1 and r≥1 on the infinite grid.