Graph Broadcast Domination
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.
Some tracks challenged my reflexes more than expected, but completing them in Friday Night Funkin after several attempts gave me a real sense of accomplishment and encouraged further improvement.
I found the article more informative than I expected, especially because it introduced several details that were completely new to me. cooking games online
Understanding router access is helpful when reviewing network preferences or wireless settings. This guide about 10.0.0.1 provides useful information about configuration options and basic administration, making router management easier to understand for everyday users.
The reason why I find Top Free Games attractive is its ability to make you keep focused on the game itself. No complicated procedures are involved when I am searching for a fast browser game. The fact that I have an opportunity to go through different games and play them right away is what makes the entire process convenient. For casual gamers, such approach is really beneficial because the only purpose of the game is fun.
Congratulations on the acceptance of your paper! The exploration of broadcast domination in the infinite lattice is fascinating. I’m eager to see how this research develops, especially its potential applications with tools like a random state generator.