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

Key words:

• Domination
• semipaired domination
• tree