Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
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], invo...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Department of Mathematics and Applied Mathematics
2017
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613450771890177 |
|---|---|
| access_status_str | Open Access |
| author | Faul, Peter |
| author2 | Erwin, David |
| author_browse | Erwin, David Faul, Peter |
| author_facet | Erwin, David Faul, Peter |
| author_sort | Faul, Peter |
| collection | Thesis |
| description | 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. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/22717 |
| institution | University of Cape Town (South Africa) |
| language | eng |
| last_indexed | 2026-06-10T12:36:20.976Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2017 |
| publishDateRange | 2017 |
| publishDateSort | 2017 |
| publisher | Department of Mathematics and Applied Mathematics |
| publisherStr | Department of Mathematics and Applied Mathematics |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/22717 Generalisations of graph broadcasts Faul, Peter Erwin, David Mathematics and Applied Mathematics 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. 2017-01-16T13:41:02Z 2017-01-16T13:41:02Z 2016 Master Thesis Masters MSc http://hdl.handle.net/11427/22717 eng application/pdf Department of Mathematics and Applied Mathematics Faculty of Science University of Cape Town |
| spellingShingle | Mathematics and Applied Mathematics Faul, Peter Generalisations of graph broadcasts |
| thesis_degree_str | Master's |
| title | Generalisations of graph broadcasts |
| title_full | Generalisations of graph broadcasts |
| title_fullStr | Generalisations of graph broadcasts |
| title_full_unstemmed | Generalisations of graph broadcasts |
| title_short | Generalisations of graph broadcasts |
| title_sort | generalisations of graph broadcasts |
| topic | Mathematics and Applied Mathematics |
| url | http://hdl.handle.net/11427/22717 |
| work_keys_str_mv | AT faulpeter generalisationsofgraphbroadcasts |