Abstract
D.Phil.
Domination in graphs is now well studied in graph theory and the literature on this
subject has been surveyed and detailed in the two books by Haynes, Hedetniemi, and
Slater [45, 46]. In this thesis, we continue the study of domination, by adding to the
theory; improving a number of known bounds and solving two previously published conjectures.
With the exception of the introduction, each chapter in this thesis corresponds to a
single paper already published or submitted as a journal article. Despite the seeming
disparity in the content of some of these articles, there are two overarching goals achieved
in this thesis. The rst is an attempt to partition the vertex set of a graph into two sets,
each holding a speci c domination-type property. The second is simply to improve known
bounds for various domination parameters. In particular, an edge weighting function is
presented which has been useful in providing some of these bounds.
Although the research began as two separate areas of focus, there has been a fair
degree of overlap and a number of the results contained in this thesis bridge the gap
quite pleasingly. Specially, Chapter 11 uses the edge weighting function to prove a
bound on one of the sets in our most fundamental partitions, while the improvement on
a known bound presented in Chapter 7 was inspired by considering the possible existence
of another partition. This latter proof relies implicitly on the `almost' existence of such
a partition.