A dominating set $D$ of a graph $G$ without isolated vertices is called semipaired dominating set if $D$ can be partitioned into $2$-element subsets such that the vertices in each set are at distance at most $2$. The semipaired domination number, denoted by $\gamma_{pr2}(G)$ is the minimum cardinality of a semipaired dominating set of $G$. Given a graph $G$ with no isolated vertices, the \textsc{Minimum Semipaired Domination} problem is to find a semipaired dominating set of $G$ of cardinality $\gamma_{pr2}(G)$. The decision version of the \textsc{Minimum Semipaired Domination} problem is already known to be NP-complete for chordal graphs, an important graph class. In this paper, we show that the decision version of the \textsc{Minimum Semipaired Domination} problem remains NP-complete for split graphs, a subclass of chordal graphs. On the positive side, we propose a linear-time algorithm to compute a minimum cardinality semipaired dominating set of block graphs. In addition, we prove that the \textsc{Minimum Semipaired Domination} problem is APX-complete for graphs with maximum degree $3$.
翻译:以 $\ gamma\\ pr2} (G) 表示的半折叠支配数是半折叠主导数的最小基数。 如果将 $D 可以分割成 $2 元素子集, 则将 $D 标定为 $2 美元 。 由 $\ gamma\\\ pr2} (G) 表示的半折叠支配数是半折叠支配数 $G 的最小基数 。 如果图形 $G 则称为 半折叠主导数 。 如果图形没有孤立的顶端, 则 $G 的半折叠主导数 。 问题在于 $2 $ 2 的半折叠分数 。 半折叠数 。 在本文中, 我们显示 textc{ mintimimimimum 半折叠成 平整数 的平整数 。