Power Domination in graphs

Reagon, Dean

Power Domination in graphs

Thesis / Dissertation

2025

Publisher

University of Cape Town

Department

Department of Mathematics and Applied Mathematics

Faculty

Faculty of Science

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.

Keywords

Domination

Graphs

Reference:

Collections

Masters

Full item page