Minimum Contagious Sets in Trees with Degree-Proportional Thresholds

Source abstract

We investigate how large the minimum size of a contagious set can be among trees of a fixed order. Given a graph $G$ and $ρ\in[0,1]$, an inactive vertex $u$ becomes active when at least $\lceil{ρd_G(u)\rceil}$ of its neighbors are active. An initial set of active vertices is contagious if the process eventually activates every vertex. We obtain exact values for the minimum size of a contagious set in perfect $d$-ary trees. We then determine the exact maximum of this minimum size over all trees of order $n$. We establish this result by bounding the number of pairwise disjoint resistant sets, each of which must intersect every contagious set, and constructing trees that attain the resulting bounds. Finally, by bounding the change in the minimum size of a contagious set under a leaf exchange, we show that, for $0<ρ\leq1$ and $n\geq2$, every integer between $1$ and this maximum occurs as the minimum size of a contagious set in a tree of order $n$.