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.

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.

Given a digraph D = (V, A), with vertex set V and arc set A, a set S ⊆ V is a dominating set if for every vertex v in V \ S, there are a vertex u in S and an arc (u, v) from u to v. In this chapter we consider the counterparts in directed graphs of independent, dominating, independent dominating, and total dominating sets in undirected graphs.

A set S of vertices in a graph G is a paired dominating set if every vertex of G is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching (not necessarily as an induced subgraph). The minimum cardinality of a paired dominating set of G is the paired domination number of G. This chapter presents a survey of the major results on paired domination with an emphasis on bounds for the paired domination number.