Vaccinate your trees!

Original · EN

For a graph G and an 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 two vaccination problems, where the goal is to maximize the minimum order of such a dynamic monopoly either by increasing the threshold value of b vertices beyond their degree, or by removing b vertices from G, where b is a given non-negative integer corresponding to a budget. We show how to solve these problems efficiently for trees.