Partial immunization of trees

Abstract For a graph G and a non-negative integer-valued function τ on its vertex set, a dynamic monopoly is a set of vertices of G such that iteratively adding to it vertices u of G that have at least τ ( u ) neighbors in it eventually yields the vertex set of G . We study the problem of maximizing the minimum order of a dynamic monopoly by increasing the threshold values of individual vertices subject to vertex-dependent lower and upper bounds, and fixing the total increase. We solve this problem efficiently for trees, which extends a result of Khoshkhah and Zaker (2015).