G-2016-22
A note on an induced subgraph characterization of domination perfect graphs
and BibTeX reference
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|\)
.
Published April 2016 , 12 pages
Publication
Document
G1622.pdf (300 KB)