Domination versus semipaired domination in trees

Abstract

In this paper, we study a parameter that is a relaxation of an important domination parameter, namely the paired domination. A set D of vertices in G is a semipaired dominating set of G if it is a dominating set of G and can be partitioned into 2-element subsets such that the vertices in each 2-set are at most distance two apart. The semipaired domination number, γ _pr2(G), is the minimum cardinality of a semipaired dominating set of G. For a graph G without isolated vertices, the domination number γ(G), the paired domination number γ _pr (G) and the semitotal domination number γ _t2(G) are related to the semipaired domination numbers by the following inequalities: γ(G) ≤ γ _t2(G) ≤ γ _pr2(G) ≤ γ _pr (G) ≤ 2γ(G). It means that 1 ≤ γ _pr2(G)/γ(G) ≤ 2. In this paper, we characterize those trees that attain the lower bound and the upper bound, respectively.

Mathematics Subject Classification (2010): 05C69.