Triggering cascades on undirected connected graphs

Consider the following cascading process on an undirected connected graph G(V,E)G(V,E). A set S of vertices, called the seeds, are active initially. Thereafter, an inactive vertex is activated when at least a ρ   fraction of its neighbors is active, where ρ∈(0,1]ρ∈(0,1]. The cascading process proceeds asynchronously until no more vertices can be activated. This paper proves the existence of at most (22+3)⌈ρ|V|⌉ seeds that can activate all vertices at the end.

► We consider threshold-based cascades on connected graphs. ► A degree-d vertex is activated when it has at least ρd active neighbors. ► We find bounds on the minimum number of seeds activating all vertices eventually. ► We use techniques of Ackerman et al. [Theoret. Comput. Sci. 411 (44–46) (2010) 4017–4022].