Limited broadcast domination
Feiran Yang · UVic’s Research and Learning Repository (University of Victoria) · 2019
Let G = (V,E) be a graph and f be a function such that f : V -> {0,1,2,..., k}. Let V_f^+ = {v : f(v) > 0}. If for every vertex v not in V_f^+ there exists a vertex w in V_f^+ such that d(v,w) ≤ f(w) then f is called a k-limited dominating broadcast of G. The sum of f(v) is called the cost of the broadcast. The minimum cost of a dominating broadcast is called the k-limited broadcast domination number of G, and is denoted by gamma_{b,k}(G). This parameter gamma_{b,k}(G) is a variation of the well-studied broadcast domination number. The value gamma_{b,k}(G) can also be defined as a solution to an integer linear programming problem. The solution to the dual problem is defined as the k-limited multipacking number. We begin with a survey of known results and background related to these broadcast domination related parameters. In Chapter 3, we give a proof of NP-completeness for the problem of determining the k-limited broadcast domination number for a fixed graph G, as well as a proof of NP-completeness for its dual problem of determining the k-limited multipacking number. Chapter 4 focuses on cubic and subcubic graphs. Here we give an upper bound for the 2-limited broadcast domination number of (C_4, C_6)-free cubic graphs. In Chapter 5, we describe algorithms which determine the k-limited broadcast domination number for strongly chordal graphs, interval graphs, circular arc graphs and proper interval bigraphs in polynomial time. In Chapter 6, we show that the k-limited broadcast domination number for trees can be determined in linear time. We specifically give a linear time algorithm which determines the 2-limited broadcast domination number of trees.