Generalisations of graph broadcasts

Simple item page
dc.contributor.advisorErwin, Daviden_ZA
dc.contributor.authorFaul, Peteren_ZA
dc.date.accessioned2017-01-16T13:41:02Z
dc.date.available2017-01-16T13:41:02Z
dc.date.issued2016en_ZA
dc.description.abstractLet 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.en_ZA
dc.identifier.apacitationFaul, P. (2016). <i>Generalisations of graph broadcasts</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics. Retrieved from http://hdl.handle.net/11427/22717en_ZA
dc.identifier.chicagocitationFaul, Peter. <i>"Generalisations of graph broadcasts."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2016. http://hdl.handle.net/11427/22717en_ZA
dc.identifier.citationFaul, P. 2016. Generalisations of graph broadcasts. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Faul, Peter AB - 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. DA - 2016 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 2016 T1 - Generalisations of graph broadcasts TI - Generalisations of graph broadcasts UR - http://hdl.handle.net/11427/22717 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/22717
dc.identifier.vancouvercitationFaul 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/22717en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Mathematics and Applied Mathematicsen_ZA
dc.publisher.facultyFaculty of Scienceen_ZA
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherMathematics and Applied Mathematicsen_ZA
dc.titleGeneralisations of graph broadcastsen_ZA
dc.typeMaster Thesis
dc.type.qualificationlevelMasters
dc.type.qualificationnameMScen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_sci_2016_faul_peter.pdf
Size:
558.27 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters