2-limited broadcast domination on grid graphs
Date
2021-07-29
Authors
Slobodin, Aaron
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Suppose there is a transmitter located at each vertex of a graph G. A k-limited broadcast on G is an assignment of the integers 0,1,...,k to the vertices of G. The integer assigned to the vertex x represents the strength of the broadcast from x, where strength 0 means the transmitter at x is not broadcasting. A broadcast of positive strength s from x is heard by all vertices at distance at most s from x. A k-limited broadcast is called dominating if every vertex assigned 0 is within distance d of a vertex whose transmitter is broadcasting with strength at least d. The k-limited broadcast domination number of G is the minimum possible value of the sum of the strengths of the broadcasts in a k-limited dominating broadcast of G.
We establish upper and lower bounds for the 2-limited broadcast domination number of various grid graphs, in particular the Cartesian products of two paths, a path and a cycle, and two cycles. The upper bounds are derived by explicit broadcast constructions for these graphs. The lower bounds are obtained via linear programming duality by finding lower bounds for the fractional 2-limited multipacking number of these graphs. Finally, we present an algorithm to improve the lower bound for the 2-limited broadcast domination number of special sub-families of grids. We conclude this thesis with suggested open problems in broadcast domination and multipackings.
Description
Keywords
graph theory, broadcast domination, k-limited broadcast domination, multipacking, fractional 2-limited multipacking, optimization, discrete math, limited broadcast domination, limited multipacking, linear programming