Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Power Domination in graphs
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English English |
| Published: |
Department of Mathematics and Applied Mathematics
2026
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613225212706816 |
|---|---|
| access_status_str | Open Access |
| author | Reagon, Dean |
| author2 | Allie, Imran |
| author_browse | Allie, Imran Reagon, Dean |
| author_facet | Allie, Imran Reagon, Dean |
| author_sort | Reagon, Dean |
| collection | Thesis |
| description | 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. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/42656 |
| institution | University of Cape Town (South Africa) |
| language | English eng |
| last_indexed | 2026-06-10T12:32:45.765Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2026 |
| publishDateRange | 2026 |
| publishDateSort | 2026 |
| 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/42656 Power Domination in graphs Reagon, Dean Allie, Imran Erwin, David Domination Graphs 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. 2026-01-22T12:11:08Z 2026-01-22T12:11:08Z 2025 2026-01-22T11:18:58Z Thesis / Dissertation Masters MSc http://hdl.handle.net/11427/42656 en eng application/pdf Department of Mathematics and Applied Mathematics Faculty of Science University of Cape Town |
| spellingShingle | Domination Graphs Reagon, Dean Power Domination in graphs |
| thesis_degree_str | Master's |
| title | Power Domination in graphs |
| title_full | Power Domination in graphs |
| title_fullStr | Power Domination in graphs |
| title_full_unstemmed | Power Domination in graphs |
| title_short | Power Domination in graphs |
| title_sort | power domination in graphs |
| topic | Domination Graphs |
| url | http://hdl.handle.net/11427/42656 |
| work_keys_str_mv | AT reagondean powerdominationingraphs |