Abstract
Ph.D.
In this thesis, our primary objective is to investigate the effects that various graph
modifications have on the total domination number of a graph. In Chapter 1, we
introduce basic graph theory concepts and preliminary definitions.
In Chapters 2 and 3, we investigate the graph modification of edge removal. In
Chapter 2, we characterize graphs for which the removal of any arbitrary edge increases
the total domination number. We also begin the investigation of graphs for
which the removal of any arbitrary edge has no effect on the total domination number.
In Chapter 3, we continue this investigation and determine the minimum number of
edges required for these graphs. The contents of Chapters 2 and 3 have been published
in Discrete Applied Mathematics [15] and [16].
In Chapter 4, we investigate the graph modification of edge addition. In particular,
we focus our attention on graphs for which adding an edge between any pair of
nonadjacent vertices has no effect on the total domination number. We characterize
these graphs, determine a sharp upper bound on their total domination number and
determine which combinations of order and total domination number are attainable.
10
11
We also study claw-free graphs which have this property. The contents of this chapter
were published in Discrete Mathematics [20].
In Chapter 5, we investigate the graph modification of vertex removal. We characterize
graphs for which the removal of any vertex changes the total domination
number and find sharp upper and lower bounds on the total domination number of
these graphs. We also characterize graphs for which the removal of an arbitrary vertex
has no effect on the total domination number and we further show that they have no
forbidden subgraphs. The contents of this chapter were published in Discrete Applied
Mathematics [14].
In Chapters 6 and 7, we investigate the graph modification of edge lifting. In
Chapter 6, we show that there are no trees for which every possible edge lift decreases
the domination number, and we characterize trees for which every possible edge lift
increases the domination number. The contents of Chapter 6 were published in the
journal Quaestiones Mathematicae [17]. In Chapter 7, we show that there are no
trees for which every possible edge lift decreases the total domination number and
that there are no trees for which every possible edge lift leaves the total domination
number unchanged. We characterize trees for which every possible edge lift increases
the total domination number. At the time of the writing of this thesis, the contents of
Chapter 7 have been published online in the Journal of Combinatorial Optimization
[18] and will appear in print in a future issue.