Algorithmic aspects of certified domination in graphs

Abstract

A dominating set $ D $ of a graph $ G=(V,E) $ is called a certified dominating set of $ G $ if $\vert N(v) \cap (V \setminus D)\vert$ is either 0 or at least 2 for all $ v \in D$. The certified domination number $\gamma_{cer}(G) $ is the minimum cardinality of a certified dominating set of $ G $. In this paper, we prove that the decision problem corresponding to $\gamma_{cer}(G) $ is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. We also prove that it is linear time solvable for chain graphs, threshold graphs and bounded tree-width graphs.