On the spread of influence in graphs.

Consider a graph G and an initial configuration where each node is black or white. Assume
that in each round all nodes simultaneously update their color based on a predefined rule.
In the r-threshold (resp. α-threshold) model, a node becomes black if at least r of its
neighbors (resp. α fraction of its neighbors) are black, and white otherwise.
A node set D is said to be a dynamic monopoly if black color takes over once all nodes
in D are black. We provide several tight bounds on the minimum size of a dynamic
monopoly in terms of different graph parameters. Furthermore, we prove some bounds
on the stabilization time of the process. Finally, we also establish bounds on the minimum
size of a dynamic monopoly and the stabilization time in the aforementioned models, as a
function of the underlying graph’s expansion