On dynamic monopolies of graphs with general thresholds

Let GG be a graph and τ:V(G)→Nτ:V(G)→N be an assignment of thresholds to the vertices of GG. A subset of vertices DD is said to be dynamic monopoly (or simply dynamo) if the vertices of GG can be partitioned into subsets D0,D1,…,DkD0,D1,…,Dk such that D0=DD0=D and for any i=1,…,k−1i=1,…,k−1 each vertex vv in Di+1Di+1 has at least t(v)t(v) neighbors in D0∪⋯∪DiD0∪⋯∪Di. Dynamic monopolies are in fact modeling the irreversible spread of influence such as disease or belief in social networks. We denote the smallest size of any dynamic monopoly of GG, with a given threshold assignment, by dyn(G). In this paper, we first define the concept of a resistant subgraph and show its relationship with dynamic monopolies. Then we obtain some lower and upper bounds for the smallest size of dynamic monopolies in graphs with different types of thresholds. Next we introduce dynamo-unbounded families of graphs and prove some related results. We also define the concept of a homogeneous society that is a graph with probabilistic thresholds satisfying some conditions and obtain a bound for the smallest size of its dynamos. Finally, we consider dynamic monopoly of line graphs and obtain some bounds for their sizes and determine the exact values in some special cases.