For a graph G = (V, E), a set S ⊆ V is a dominating set if every vertex in V - S is adjacent to at least one vertex in S. A dominating set S ⊆ V is a paired-dominating set if the induced subgraph 〈S〉 has a perfect matching. We introduce a variant of paired-domination where an additional restriction is placed on the induced subgraph 〈S〉. A paired-dominating set S is an induced-paired dominating set if the edges of the matching are the induced edges of 〈S〉, that is, 〈S〉 is a set of independent edges. The minimum cardinality of an induced-paired dominating set of G is the induced-paired domination number γip(G). Every graph without isolates has a paired-dominating set, but not all these graphs have an induced-paired dominating set. We show that the decision problem associated with induced-paired domination is NP-complete even when restricted to bipartite graphs and give bounds on γip(G). A characterization of those triples (a, b, c) of positive integers a ≤ b ≤ c for which a graph has domination number a, paired-domination number b, and induced-paired domination c is given. In addition, we characterize the cycles and trees that have induced-paired dominating sets.

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.

In this paper, we continue the study of the domination game in graphs introduced by Brešar, Klavžar, and Rall [SIAM J. Discrete Math. 24 (2010) 979-991]. We study the paired-domination version of the domination game which adds a matching dimension to the game. This game is played on a graph G by two players, named Dominator and Pairer. They alternately take turns choosing vertices of G such that each vertex chosen by Dominator dominates at least one vertex not dominated by the vertices previously chosen, while each vertex chosen by Pairer is a vertex not previously chosen that is a neighbor of the vertex played by Dominator on his previous move. This process eventually produces a paired-dominating set of vertices of G; that is, a dominating set in G that induces a subgraph that contains a perfect matching. Dominator wishes to minimize the number of vertices chosen, while Pairer wishes to maximize it. The game paired-domination number γgpr(G) of G is the number of vertices chosen when Dominator starts the game and both players play optimally. Let G be a graph on n vertices with minimum degree at least 2. We show that γgpr(G) ≤ 45 n, and this bound is tight. Further we show that if G is (C4, C5)-free, then γgpr(G) ≤ 43 n, where a graph is (C4, C5)-free if it has no induced 4-cycle or 5-cycle. If G is 2-connected and bipartite or if G is 2-connected and the sum of every two adjacent vertices in G is at least 5, then we show that γgpr(G) ≤ 34 n.

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G is bounded above by twice the domination number of G. We give a constructive characterization of the trees attaining this bound.

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, and a double dominating set is a dominating set that dominates every vertex of G at least twice. We show that for trees, the paired-domination number is less than or equal to the double domination number, solving a conjecture of Chellali and Haynes. Then we characterize the trees having equal paired and double domination numbers.

A paired dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, and a double dominating set is a dominating set that dominates every vertex of G at least twice. First a necessary and sufficient condition is given for a double dominating set (respectively, paired dominating set) to be minimal in G. We show that for clawfree graphs, the paired domination number is less than or equal to the double domination number. Then bounds on the double and paired domination numbers are presented. Sums involving these parameters are also considered.

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching. We characterize the trees having unique minimum paired-dominating sets.

Let G be a graph with vertex set V and no isolated vertices. A subset S ⊆ V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. We present a method of building trees having a unique minimum semipaired dominating set.

Let G be a graph with vertex set V and no isolated vertices. A subset S ⊆ V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γ pr2 (G) is the minimum cardinality of a semipaired dominating set of G. We show that if G is a connected graph G of order n ≥ 3, then γ pr2 (G) ≤ 32 n, and we characterize the extremal graphs achieving equality in the bound.

Let G be a graph with vertex set V. A subset S ? V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number is the minimum cardinality of a semipaired dominating set of G. We characterize the trees having a unique minimum semipaired dominating set. We also determine an upper bound on the semipaired domination number of these trees and characterize the trees attaining this bound.