Perfect graphs of strong domination and independent strong domination (Q1841911): Difference between revisions

A graph \(G\) is called domination perfect if for every induced subgraph \(H\) of \(G\) the domination number of \(H\) equals the independent domination number of \(H\). Such equalities among four parameters, namely domination number, strong domination number, independent domination number and independent strong domination number, lead to six possible perfection classes of graphs, several subclasses of which are characterized in this paper via forbidden induced subgraphs. Furthermore it is shown that the problems of deciding whether for a given graph \(G\) and a given integer \(k\) there is a strong dominating set, independent strong dominating set, or weak dominating set, of \(G\) of cardinality at most \(k\) are NP-complete. Several open problems and conjectures are proposed.