加载中…
Given a graph , is a dominating set if every $v\in V\setminus SS$. The Minimum Dominating Set problem asks for a dominating set with minimum cardinality. It is well known that its decision version is -complete even when is a claw-free graph. We give a complexity dichotomy for the Minimum Dominating Set problem for the class of -free graphs when has at most six vertices. In an intermediate step we show that the Minimum Dominating Set problem is -complete for cubic graphs.

生成讲解博客的中文版本

生成AI智能校验的中文版本