Abstract
D.Phil. (Mathematics)
Domination and its variants are now well studied in graph theory. One of these
variants, paired-domination, requires that the subgraph induced by the dominating
set contains a perfect matching. In this thesis, we further investigate the concept of
paired-domination. Chapters 2, 3, 4, and 5 of this thesis have been published in [17],
[41], [42], and [43], respectively, while Chapter 6 is under submission; see [44].
In Chapter 1, we introduce the domination parameters we use, as well as the
necessary graph theory terminology and notation. We combine the de nition of a
paired-dominating set and a locating set to de ne three new sets: locating-paired-
dominating sets, di erentiating-paired-dominating sets, and metric-locating-paired-
dominating sets. We use these sets in Chapters 3 and 4.
In Chapter 2, we investigate the relationship between the upper paired-domination
and upper total domination numbers of a graph. In Chapter 3, we study the properties
of the three kinds of locating paired-dominating sets we de ned, and in Chapter 4 we
give a constructive characterisation of those trees which do not have a di erentiating-
paired-dominating set. In Chapter 5, we study the problem of characterising planar
graphs with diameter two and paired-domination number four. Lastly, in Chap-
ter 6, we establish an upper bound on the size of a graph of given order and paired-
domination number and we characterise the extremal graphs that achieve equality in
the established bound.