{"id":{"repo_id":"cape-town","oai_identifier":"oai:open.uct.ac.za:11427/42656"},"canonical_url":"https://search.dev.ndltd.org/etd/cape-town/oai:open.uct.ac.za:11427/42656","repository":{"repo_id":"cape-town","name":"University of Cape Town","base_url":"https://open.uct.ac.za/oai/request"},"display":{"title":"Power Domination in graphs","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Reagon, Dean"],"institution":"Department of Mathematics and Applied Mathematics","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Allie, Imran","Erwin, David"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025","date_published":"2025","updated_at":"2026-07-22T22:23:00Z","subjects":["Domination","Graphs"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11427/42656","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Allie, Imran","Erwin, David"]},{"key":"dc:creator","label":"Author","values":["Reagon, Dean"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-01-22T12:11:08Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-01-22T12:11:08Z"]},{"key":"dc:date.issued","label":"Date","values":["2025"]},{"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":["Thesis / Dissertation"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Masters","MSc"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Domination","Graphs"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11427/42656"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Power Domination in graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Allie, Imran","Erwin, David"],"dc:creator":["Reagon, Dean"],"dc:date.accessioned":["2026-01-22T12:11:08Z"],"dc:date.available":["2026-01-22T12:11:08Z"],"dc:date.issued":["2025"],"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.uri":["http://hdl.handle.net/11427/42656"],"dc:language.iso":["en"],"dc:publisher.department":["Department of Mathematics and Applied Mathematics"],"dc:publisher.institution":["University of Cape Town"],"dc:subject":["Domination","Graphs"],"dc:title":["Power Domination in graphs"],"dc:type":["Thesis / Dissertation"],"dc:type.qualificationlevel":["Masters","MSc"]},"updated_at":"2026-07-22T22:23:00Z"}