





















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。