Groupe d’études et de recherche en analyse des décisions

A note on an induced subgraph characterization of domination perfect graphs

Eglantine Camby et Fränk Plein

Let $$\gamma(G)$$ and $$\iota(G)$$ be the domination and independent domination numbers of a graph $$G$$, respectively. Introduced by Sumner and Moorer (1979), a graph $$G$$ is domination perfect if $$\gamma(H) = \iota(H)$$ for every induced subgraph $$H \subseteq G$$. In 1991, Zverovich and Zverovich (1991)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 $$|Y| \leq |D|$$.

, 12 pages