On domination and reinforcement numbers in trees

The reinforcement number of a graph is the smallest number of edges that have to be added to a graph to reduce the domination number. We introduce the k-reinforcement number of a graph as the smallest number of edges that have to be added to a graph to reduce the domination number by k. We present an O(k^2n) dynamic programming algorithm for computing the maximum number of vertices that can be dominated using @c(G)-k dominators for trees. A corollary of this is a linear-time algorithm for computing the k-reinforcement number of a tree. We also discuss extensions and related problems.