In this paper, we consider the r-dominating set problem on graphs which can
be generated from the one-vertex graph by a finite number of homogeneous e
xtensions and by attaching pendant vertices. We show that for such graphs a
minimum cardinality r-dominating set can be computed in O(\V\ \E\) time; f
or distance-hereditary graphs-a proper subclass-we even get a linear time a
lgorithm. Furthermore, since these graph classes are closed under adding fa
lse twins, a total dominating set can be computed in the same time bound. (
C) 2001 John Wiley & Sons, Inc.