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(k2n)O(k2n) dynamic programming algorithm for computing the maximum number of vertices that can be dominated using γ(G)-kγ(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.