Generalisations of graph broadcasts

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.

Grantor dc:publisher.institution

Department of Mathematics and Applied Mathematics

Year dc:date.issued

2016

Author dc:creator

• Faul, Peter

Advisor dc:contributor.advisor

• Erwin, David

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/11427/22717

OAI identifier oai:identifier

oai:open.uct.ac.za:11427/22717