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.

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.

A Roman dominating function (RDF) on a graph G is a function f : V (G) → (0, 1,2) satisfying the condition that every vertex u with f(u) = 0 is adjacent to at least one vertex v of G for which f(v) = 2. The weight of a Roman dominating function is the sum f(V ) = Σv∈Vf(v), and the minimum weight of a Roman dominating function f is the Roman domination number γR(G). An RDF f is called an independent Roman dominating function (IRDF) if the set of vertices assigned positive values under f is independent. The independent Roman domination number iR(G) is the minimum weight of an IRDF on G. We show that for every nontrivial connected graph G with maximum and i(G) are, respectively, the domination and independent domination numbers of G. Moreover, we characterize the connected graphs attaining each lower bound. We give an additional lower bound for γR(G) and compare our two new bounds on γR(G) with some known lower bounds.

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.

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.

We mainly study two related dominating functions, namely, the weak Roman and 2-rainbow dominating functions. We show that for all graphs, the weak Roman domination number is bounded above by the 2-rainbow domination number. We present bounds on the weak Roman domination number and the secure domination number in terms of the total domination number for specific families of graphs, and we show that the 2-rainbow domination number is bounded below by the total domination number for trees and for a subfamily of cactus graphs.

In this paper, we initiate the study of a variant of Roman dominating functions. For a graph G=(V,E), a Roman {2}-dominating function f:V→{0,1,2} has the property that for every vertex v∈V with f(v)=0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to least two vertices assigned 1 under f. The weight of a Roman {2}-dominating function is the sum Σv∈Vf(v), and the minimum weight of a Roman {2}-dominating function f is the Roman {2}-domination number. First, we present bounds relating the Roman {2}-domination number to some other domination parameters. In particular, we show that the Roman {2}-domination number is bounded above by the 2-rainbow domination number. Moreover, we prove that equality between these two parameters holds for trees and cactus graphs with no even cycles. Finally, we show that associated decision problem for Roman {2}-domination is NP-complete, even for bipartite graphs.

In a graph G = (V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ε E(Ḡ), the double domination number of G + uv is less than the double domination number of G. We investigate double domination edge critical graphs and characterize the trees and cycles having this property. Then we concentrate on double domination edge critical graphs having small double domination numbers. In particular, we characterize the ones with double domination number three and subfamilies of those with double domination number four.