We analyse approximation algorithms (greedy heuristics) for the classical domination number and two multiple domination numbers in simple graphs. First, we present a short self-contained proof of the known result that the minimum domination problem in any graph G with maximum degree ∆ can be solved within the approximation ratio of ln(∆ + 1) + 1. The proof is based on an analysis of a simple greedy heuristic. Then, by analysing more advanced greedy heuristic techniques and using ideas from our self-contained proof for the classical domination number, we fix a gap in the existing proof of a similar result for the k-tuple domination number. That is, we prove that the minimum k-tuple domination problem indeed can be approximated within the ratio of ln(∆+1)+1. The proof of this result is self-contained, direct, and much shorter than the existing proof, which contains the gap. Finally, we show that the known approximation ratio of ln(2∆)+1 for the minimum k-domination problem can be improved to a better ratio.

We show that all results stated in [E. Camby, F. Plein, Discrete Appl. Math. 217 (2017) 711–717] are either previously known or incorrect. For example, Camby and Plein claimed to provide counterexamples to the 1995 characterization of domination perfect graphs due to Zverovich and Zverovich; however, these counterexamples are not valid. Moreover, the new characterization of domination perfect graphs proposed in that paper is incorrect.For completeness, we present a relatively brief proof of the 1995 characterization of domination perfect graphs due to Zverovich and Zverovich.