Article ID Journal Published Year Pages File Type
4949775 Discrete Applied Mathematics 2017 7 Pages PDF
Abstract
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|≤∣D∣.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A note on an induced subgraph characterization of domination perfect graphs
Authors
, ,