Graph Broadcast Domination

An optimal (2,3) broadcast.

Paper with Timothy Randolph and Ben Drews (Williams class of '18) has been accepted for publication in Discrete Applied Mathematics. A preprint can be found here.

In this paper we studied broadcast domination of the infinite lattice (grid graph with integer lattice points). The abstract of this work follows:

Let G = (V, E) be a graph and t, r be positive integers. Then 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 T ⊆ V such that the sum of all signal received at each vertex v ∈ V is at least r. We say that T is optimal if |T| is minimal among all such sets T. 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 Gare 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 mand 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.