• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

2-limited broadcast domination on grid graphs

Slobodin, Aaron 29 July 2021 (has links)
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. / Graduate

Page generated in 0.1349 seconds