{"id":{"repo_id":"cape-town","oai_identifier":"oai:open.uct.ac.za:11427/22717"},"canonical_url":"https://search.dev.ndltd.org/etd/cape-town/oai:open.uct.ac.za:11427/22717","repository":{"repo_id":"cape-town","name":"University of Cape Town","base_url":"https://open.uct.ac.za/oai/request"},"display":{"title":"Generalisations of graph broadcasts","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Faul, Peter"],"institution":"Department of Mathematics and Applied Mathematics","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Erwin, David"],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016","date_published":"2016","updated_at":"2026-07-22T22:23:31Z","subjects":[],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11427/22717","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Erwin, David"]},{"key":"dc:creator","label":"Author","values":["Faul, Peter"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2017-01-16T13:41:02Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2017-01-16T13:41:02Z"]},{"key":"dc:date.issued","label":"Date","values":["2016"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Department of Mathematics and Applied Mathematics"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cape Town"]},{"key":"dc:type","label":"Dc Type","values":["Master Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Masters"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["MSc"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11427/22717"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Generalisations of graph broadcasts"]}]}],"canonical_facts":{"dc:contributor.advisor":["Erwin, David"],"dc:creator":["Faul, Peter"],"dc:date.accessioned":["2017-01-16T13:41:02Z"],"dc:date.available":["2017-01-16T13:41:02Z"],"dc:date.issued":["2016"],"dc:description.abstract":["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."],"dc:identifier.uri":["http://hdl.handle.net/11427/22717"],"dc:language.iso":["eng"],"dc:publisher.department":["Department of Mathematics and Applied Mathematics"],"dc:publisher.institution":["University of Cape Town"],"dc:title":["Generalisations of graph broadcasts"],"dc:type":["Master Thesis"],"dc:type.qualificationlevel":["Masters"],"dc:type.qualificationname":["MSc"]},"updated_at":"2026-07-22T22:23:31Z"}