Power Domination in graphs
| dc.contributor.advisor | Allie, Imran | |
| dc.contributor.advisor | Erwin, David | |
| dc.contributor.author | Reagon, Dean | |
| dc.date.accessioned | 2026-01-22T12:11:08Z | |
| dc.date.available | 2026-01-22T12:11:08Z | |
| dc.date.issued | 2025 | |
| dc.date.updated | 2026-01-22T11:18:58Z | |
| dc.description.abstract | Domination in graphs has been studied since the 1800s. Many parameters related to domination have been defined and studied since then. Power domi-nation was first defined and studied in the early 2000s. It is an abstraction of how an electrical power system is monitored. In this thesis, we focus on power domination and its natural extension k-power domination. We also look at the propagation radius, which is essentially the number of steps it takes a power dominating set of vertices to monitor a graph. We show how ideas from domina-tion can be extended to power domination and k-power domination. We show how domination differs from k-power domination. We demonstrate how making small changes to a graph affects the domination and power domination number of the graph. The small graph changes we will present are: vertex removal, edge removal and edge contraction. We present upper and lower bounds for how much the power domination number can change and present examples that reach all of these bounds. We present a general bound on the power domination and k-power domination number of connected graphs. We also present a general bound on the power domination number of connected, claw-free, cubic graphs. In all cases we present examples that reach these bounds. We show that finding a power dominating set of a tree is equivalent to finding a spider partition of that tree. We also present a lower bound on the power domination number of a tree with respect to its number of branching vertices. We present an upper bound on the power domination radius with regards to the smallest degree of a vertex in a graph. We also present infinitely many graphs that reach this bound. | |
| dc.identifier.apacitation | Reagon, D. (2025). <i>Power Domination in graphs</i>. (). University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics. Retrieved from http://hdl.handle.net/11427/42656 | en_ZA |
| dc.identifier.chicagocitation | Reagon, Dean. <i>"Power Domination in graphs."</i> ., University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2025. http://hdl.handle.net/11427/42656 | en_ZA |
| dc.identifier.citation | Reagon, D. 2025. Power Domination in graphs. . University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics. http://hdl.handle.net/11427/42656 | en_ZA |
| dc.identifier.ris | TY - Thesis / Dissertation AU - Reagon, Dean AB - Domination in graphs has been studied since the 1800s. Many parameters related to domination have been defined and studied since then. Power domi-nation was first defined and studied in the early 2000s. It is an abstraction of how an electrical power system is monitored. In this thesis, we focus on power domination and its natural extension k-power domination. We also look at the propagation radius, which is essentially the number of steps it takes a power dominating set of vertices to monitor a graph. We show how ideas from domina-tion can be extended to power domination and k-power domination. We show how domination differs from k-power domination. We demonstrate how making small changes to a graph affects the domination and power domination number of the graph. The small graph changes we will present are: vertex removal, edge removal and edge contraction. We present upper and lower bounds for how much the power domination number can change and present examples that reach all of these bounds. We present a general bound on the power domination and k-power domination number of connected graphs. We also present a general bound on the power domination number of connected, claw-free, cubic graphs. In all cases we present examples that reach these bounds. We show that finding a power dominating set of a tree is equivalent to finding a spider partition of that tree. We also present a lower bound on the power domination number of a tree with respect to its number of branching vertices. We present an upper bound on the power domination radius with regards to the smallest degree of a vertex in a graph. We also present infinitely many graphs that reach this bound. DA - 2025 DB - OpenUCT DP - University of Cape Town KW - Domination KW - Graphs LK - https://open.uct.ac.za PB - University of Cape Town PY - 2025 T1 - Power Domination in graphs TI - Power Domination in graphs UR - http://hdl.handle.net/11427/42656 ER - | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/11427/42656 | |
| dc.identifier.vancouvercitation | Reagon D. Power Domination in graphs. []. University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2025 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/42656 | en_ZA |
| dc.language.iso | en | |
| dc.language.rfc3066 | eng | |
| dc.publisher.department | Department of Mathematics and Applied Mathematics | |
| dc.publisher.faculty | Faculty of Science | |
| dc.publisher.institution | University of Cape Town | |
| dc.subject | Domination | |
| dc.subject | Graphs | |
| dc.title | Power Domination in graphs | |
| dc.type | Thesis / Dissertation | |
| dc.type.qualificationlevel | Masters | |
| dc.type.qualificationlevel | MSc |