论文标题
在Cutic和（Claw，H）中的最小统治集中
On Minimum Dominating Sets in cubic and (claw,H)-free graphs
论文作者
论文摘要
给定图形$ g =（v，e）$，$ s \ subseteq v $，如果v \ setminus s $中的每个$ v \ aught of $ s $的元素相邻，则是一个主体集。最低统治设置问题要求具有最低基数的主导套装。众所周知，即使$ g $是无爪形的图，它的决策版本也是$ NP $ -COMPLETE。对于$ h $最多有六个顶点时，我们为$（Claw，h）$ - 免费图的最小主导设置问题提供了复杂性二分法。在一个中间步骤中，我们表明，最小主导设置问题是Cubic Graphs的$ NP $ complete。
Given a graph $G=(V,E)$, $S\subseteq V$ is a dominating set if every $v\in V\setminus S$ is adjacent to an element of $S$. The Minimum Dominating Set problem asks for a dominating set with minimum cardinality. It is well known that its decision version is $NP$-complete even when $G$ is a claw-free graph. We give a complexity dichotomy for the Minimum Dominating Set problem for the class of $(claw, H)$-free graphs when $H$ has at most six vertices. In an intermediate step we show that the Minimum Dominating Set problem is $NP$-complete for cubic graphs.
