On the spread of influence in graphs.

Abstract

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 Show more