Let G be a graph with vertex set V (G) and edge set E(G). A dominating set S of a graph G is a subset of V (G) such that each vertex in V (G) is either in S itself or adjacent to a vertex in S. Domination and its variants have been well studied [11]. One variation introduced by Erwin in [9], involves studying a function f : V (G) → {0, 1, 2, ...} called a broadcast. We say a broadcast is dominating if for each vertex v there exists a vertex u with f(u) ≠ 0 and dG(v, u) ≤ f(u). The cost of a broadcast f is given by ∑v∈V(G) f(v) and we are usually interested in what the minimum cost is over all dominating broadcasts. In a broadcast the cost to dominatate distance k is k. In this thesis we consider two models in which this need not be the case. The one model equips a graph with a cost function. This approach has been considered before in [14]. The other model equips the graph with a scaling function. We find a connection between the two frameworks, which links them in such a way that each framework proves results about the other.
Reference:
Faul, P. 2016. Generalisations of graph broadcasts. University of Cape Town.
Faul, P. (2016). Generalisations of graph broadcasts. (Thesis). University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics. Retrieved from http://hdl.handle.net/11427/22717
Faul, Peter. "Generalisations of graph broadcasts." Thesis., University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2016. http://hdl.handle.net/11427/22717
Faul P. Generalisations of graph broadcasts. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2016 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/22717