2020/02/27 by Valentin Bouquet, François Delbot, Bouquet, Valentin +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2002.12232
Given a graph G=(V,E), S⊆ V is a dominating set if every v∈ V∖ 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.