•  
  •  
 

Abstract

Let G = (V,E) be a graph and t,r be positive integers. The signal that a tower vertex T of signal strength t supplies to a vertex v is defined as sig(T, v) = max(t − dist(T,v),0), where dist(T,v) 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 T ⊆ V such that the sum of all signal received at each vertex v ∈ V from the set of towers T is at least r. The (t, r) broadcast domination number of a finite graph G, denoted γt,r(G), is the minimum cardinality over all (t,r) broadcasts for G.

Recent research has focused on bounding the (t, r) broadcast domination number for the m×n grid graph Gm,n. In 2014, Grez and Farina bounded the k-distance domination number for grid graphs, equivalent to bounding γt,1(Gm,n). In 2015, Blessing et al. established bounds on γ2,2(Gm,n), γ3,2(Gm,n), and γ3,3(Gm,n). In this paper, we take the next step and provide a tight upper bound on γt,2(Gm,n) for all t > 2. We also prove the conjecture of Blessing et al. that their bound on γ3,2(Gm,n) is tight for large values of m and n.

Author Bio

Tim Randolph is a senior at Williams College, majoring in mathematics, computer science, and philosophy. In the fall, he will begin his PhD research in theoretical computer science at Columbia University. This work was completed during the spring of his senior year as a continuation of research work done with Professor Pamela E. Harris and Benjamin Drews in the fall. In his free time, he enjoys literature, traditional animation, and triathlon training.

Download

Share

COinS