Abstract
Determining the Total Domination Number of a graph is a NP-Hard problem, with the time to generate a solution scaling impractically unless P = NP. This thesis seeks to improve the real-world runtimes of existing Total Domination algorithms by introducing a preprocessing step. We develop a novel similarity measure between vertices, which enables our algorithm to condense graphs while retaining relevant characteristics. Our approach is based on the concept of quotient graphs, but is less restrictive. In the worst case, our algorithm's runtime scales quadratically with graph order, offering a preprocessing step that may enhance existing algorithms.
Application of Quotient Graphs in Total Domination was my senior Honors Project at Moravian University. The project encompassed a year worth of research from Spring to Fall 2024. As part of the Honors Program, I wrote and defended a Thesis which can be found below.
Part of my process which I greatly recommend to any undergraduate was to document all my work in a git repository (available upon request). With a little bit of shell scripting, I was able to generate nice weekly reports with the makefile target below
updates/%.html: updates/%.md
@# parse start and stop dates from filename (format YYYY-MM-DD:YYYY-MM-DD.md)
$(eval START_DATE := $(shell echo $* | cut -d'_' -f1))
$(eval END_DATE := $(shell echo $* | cut -d'_' -f2))
@# get commits and append to to the end of file
git log --since="$(START_DATE)" --until="$(END_DATE)" \
--pretty=format:'### %h: %s%n* Author: %an%n* %ad%n%n%b' |\
sed '1s/^/\n### Commits\n/' | cat "$<" - | pandoc --metadata title="$*" -so "$@"