Broadcasting in Strong Grids

We study abstract networks called graphs, collections of nodes and connections between certain pairs of nodes. Specifically, we study an optimization problem for graphs called broadcasting, in which transmitters are placed on nodes of a graph with the goal of allowing every node to “hear” a signal. A node hears a signal from a transmitter if it is sufficiently close to the transmitting node or if the signal is sufficiently powerful. One solution to this problem is to place a transmitter on every node. However, additional and more powerful transmitters cost more. An optimal solution to the problem has a minimum cost. To understand the optimal solution, we use a second optimization problem called packing. In packing, we want to place resources in the graph so that none of the resources are too close together. For example, if our graph modelled an area of land and we wanted to find the maximum number of grizzly bears that would fit in that area without having overlapping territories, this would be a packing problem. It turns out that packing and broadcasting problems are related. In some special graphs, the maximum packing number is equal to the minimum broadcasting number. We prove this property for one such type of graph called a strong grid