论文标题
在弦图的某些子类中的半齐射支配
Semipaired Domination in Some Subclasses of Chordal Graphs
论文作者
论文摘要
如果可以将$ d $划分为$ 2 $ element子集，则不带隔离顶点的图$ g $的统治套装$ d $称为半偏用统治集，以便每个集合中的顶点最多为$ 2 $。半偏统称编号，用$γ_{pr2}（g）$表示，是半偏用$ g $的统治组的最小基数。给定一个没有孤立顶点的图形$ g $，\ textsc {最小半段统治}问题是找到一组$ g $ of $ g $ dimpinatie $ g $ gubγ_{pr2}（g）$。 \ textsc {最小半段统治}问题的决策版本已经众所周知，对于Conordal Graph（一个重要的图形类）而言，已知是NP完整的。在本文中，我们表明\ textsc {最小半段的统治}的决策版本仍然是splage graphs的NP complete，这是弦弦图的一个子类。在正面，我们提出了一种线性时间算法来计算最小基数半段的块图集。此外，我们证明\ textsc {最小半段统治}问题对于最高度量$ 3 $的图表是APX-Complete。
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 $γ_{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 $γ_{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$.
