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 γpr 2(G) is the minimum cardinality of a semipaired dominating set of G. We show that if G is a connected graph of order n with minimum degree at least 2, then γpr2(G)≤12(n+1). Further, we show that if n≢3(mod4), then γpr2(G)≤12n, and we show that for every value of n≡3(mod4), there exists a connected graph G of order n with minimum degree at least 2 satisfying γpr2(G)=12(n+1). As a consequence of this result, we prove that every graph G of order n with minimum degree at least 3 satisfies γpr2(G)≤12n.

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.

Let G be a graph with vertex set V and no isolated vertices, and let S be a dominating set of V. The set S is a semitotal dominating set of G if every vertex in S is within distance 2 of another vertex of S. And, S is a semipaired dominating set of G if S can be partitioned into 2-element subsets such that the vertices in each 2-set are at most distance two apart. The semitotal domination number γt 2(G) is the minimum cardinality of a semitotal dominating set of G, and the semipaired domination number γpr 2(G) is the minimum cardinality of a semipaired dominating set of G. For a graph without isolated vertices, the domination number γ(G) , the total domination γt(G) , and the paired domination number γpr(G) are related to the semitotal and semipaired domination numbers by the following inequalities: γ(G) ≤ γt 2(G) ≤ γt(G) ≤ γpr(G) and γ(G) ≤ γt 2(G) ≤ γpr 2(G) ≤ γpr(G) ≤ 2 γ(G). Given two graph parameters μ and ψ related by a simple inequality μ(G) ≤ ψ(G) for every graph G having no isolated vertices, a graph is (μ, ψ) -perfect if every induced subgraph H with no isolated vertices satisfies μ(H) = ψ(H). Alvarado et al. (Discrete Math 338:1424–1431, 2015) consider classes of (μ, ψ) -perfect graphs, where μ and ψ are domination parameters including γ, γt and γpr. We study classes of perfect graphs for the possible combinations of parameters in the inequalities when γt 2 and γpr 2 are included in the mix. Our results are characterizations of several such classes in terms of their minimal forbidden induced subgraphs.

In honor of Professor Peter Slater's work on paired domination, we introduce a relaxed version of paired domination, namely semipaired domination. 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. In this paper, we study the semipaired domination versus other domination parameters. For example, we show that γ(G) ≤ γPr2(G) ≤ 2γ(G) and 2/3γt(G) ≤ γPr2(T) ≤ γ 4/3γt(G), where γ(G) and γt(G) denote the domination and total domination numbers of G. We characterize the trees G for which γPr2(G) = 2γ(G).

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.

Every graph G = (V, E) has a dominating set S ⊆ V(G) such that any vertex not in S is adjacent to a vertex in S. We define a paired-dominating set S to be a dominating set S = {v1, v2,..., v2t-1, v2t} where M = {v1v2, v3v4, ..., v2t-1v2t} is a perfect matching in 〈S〉, the subgraph induced by S. The domination number of a graph G is the smallest cardinality of any dominating set of G, and the paired-domination number is the smallest cardinality of any paired-dominating set. Determining the domination number for grid graphs is a well-known open problem in graph theory. Not surprisingly, determining the paired-domination number for grid graphs is also a difficult problem. In this thesis, we survey past research in domination, paired-domination and grid graphs to obtain background for our study of paired-domination in grid graphs. We determine the paired-domination number for grid graphs Gr,c where r ∈ {2,3}, for infinite dimensional grid graphs, and for the complement of a grid graph.

The Queen’s domination problem has a long and rich history. The problem can be simply stated as: What is the minimum number of queens that can be placed on a chessboard so that all squares are attacked or occupied by a queen? The problem has been expanded to include not only the standard 8x8 board, but any rectangular m×n sized board. In this thesis, we consider both paired and total domination versions of this renowned problem.

We determine upper bounds on the ratios of several domination parameters in trees.