Algorithm and hardness result for semipaired domination in graphs

For a graph G with no isolated vertices, a dominating set D of G is called a semipaired dominating set of G if D can be partitioned into 2-element subsets such that the vertices in each 2-element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by pr2(G). The Minimum Semipaired Domination problem is to find a semipaired dominating set of G of cardinality pr2(G). Given a graph G and a positive integer k, the Semipaired Domination Decision problem is to decide whether G has a semipaired dominating set of cardinality at most k. In this paper, we show that the Semipaired Domination Decision problem is NPcomplete even for split graphs, an important subclass of chordal graphs. On the positive side, we propose a linear-time algorithm to solve the Minimum Semipaired Domination problem in trees.