A characterization of domination reducible graphs (Q1889837)

Let \(G=(V,E)\) be a graph. A set \(D\subseteq V(G)\) is dominating in \(G\) if every vertex of \(V(G)\setminus D\) is adjacent to some vertex of \(D\). The minimum cardinality of a dominating set in \(G\) is called the domination number of \(G\). And a set \(W\subseteq V(G)\) is called homogeneous in \(G\) if (a) \(2\leq|W|\leq|V(G)|-1\), and (b) \(N(x)\setminus W=N(y)\setminus W\) for each \(x,y\in W\), where \(N(v)\) denotes the neighborhood of vertex \(v\) in \(C\) (Definition 1). Moreover \(G\) is called a domination reducible graph if every induced subgraph \(H\) of \(G\) satisfies at least one of the following conditions: (a) \(\overline H\) is a disconnected graph, (b) \(H\) is a disconnected graph, (c) there is a dominating set \(D\subseteq V(H)\) of order 4 that induces \(P_4\), or (d) \(H\) has a homogeneous set \(W\) that is not simple (Definition 2). The author introduces a hereditary class of domination reducible graphs and he proves that the problem of finding the minimum dominating set is polynomial-time solvable (Proposition 1). To characterize this class structurally the author uses additional concepts (Definitions 3, 4 and 5), e.g. the concept of a reducing \(W\)-pseudopath, and together with the application of a theorem of himself in an other publication (in the present paper: Theorem 2) he gets by an extensive proof the main result of the paper by a characterization by forbidden subgraphs, namely Theorem 1: A graph \(G\) is a domination reducible graph if and only if \(G\) has no induced subgraphs isomorphic to \(G_1,G_2,\dots,G_6\), whose figures are given in the present paper. Finally two conjectures are formulated. Conjecture 1: The maximum stable set problem for domination reducible graphs can be solved in polynomial time. And the more general Conjecture 2 reads: Let \({\mathfrak P}\) be a hereditary class. If the minimum dominating set problem for \({\mathfrak P}\) can be solved in polynomial time then the maximum stable set problem for \({\mathfrak P}\) can also be solved in polynomial time.