2018/05/15 by Timothy W. Randolph, Randolph, Timothy W.
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1805.06058
openalex publication_date 2018/05/15 · 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\nthat a tower vertex T of signal strength t supplies to a vertex v is\ndefined as sig(T,v)=max(t-dist(T,v),0), where dist(T,v) denotes the\ndistance between the vertices v and T. In 2015 Blessing, Insko, Johnson,\nand Mauretour defined a \(t,r) broadcast dominating set, or simply a\n\(t,r) broadcast, on G as a set mathbbT\⊆ V such that the\nsum of all signals received at each vertex v \∈ V from the set of towers\n mathbbT is at least r. The (t,r) broadcast domination number of a\nfinite graph G, denoted \γt,r(G), is the minimum cardinality over\nall (t,r) broadcasts for G.\n Recent research has focused on bounding the (t,r) broadcast domination\nnumber for the m \× n grid graph Gm,n. In 2014, Grez and Farina\nbounded the k-distance domination number for grid graphs, equivalent to\nbounding \γt,1(Gm,n). In 2015, Blessing et al. established bounds\non \γ2,2(Gm,n), \γ3,2(Gm,n), and\n\γ3,3(Gm,n). In this paper, we take the next step and provide a\ntight upper bound on \γt,2(Gm,n) for all t>2. We also prove the\nconjecture of Blessing et al. that their bound on \γ3,2(Gm,n) is\ntight for large values of m and n.\n