摘要

Let gamma (G) and I(G) be the domination and independent domination numbers of a graph G, respectively. Introduced by Sumner and Moore (1979), a graph G is domination perfect if gamma (H) = I(H) for every induced subgraph H subset of G. In 1991, Zverovich and Zverovich proposed a characterization of domination perfect graphs in terms of forbidden induced subgraphs. Fulman (1993) noticed that this characterization is not correct. Later, Zverovich and Zverovich (1995) offered such a second characterization with 17 forbidden induced subgraphs. However, the latter still needs to be adjusted. In this paper, we point out a counterexample. We then give a new characterization of domination perfect graphs in terms of only 8 forbidden induced subgraphs and a short proof thereof. Moreover, in the class of domination perfect graphs, we propose a polynomial-time algorithm computing, given a dominating set D, an independent dominating set Y such that vertical bar Y vertical bar <= vertical bar D vertical bar.

  • 出版日期2017-1-30