On dynamic monopolies of graphs: The average and strict majority thresholds

Let GG be a graph and τ:V(G)→N∪{0}τ:V(G)→N∪{0} be an assignment of thresholds to the vertices of GG. A subset of vertices DD is said to be a dynamic monopoly corresponding to (G,τ)(G,τ) if the vertices of GG can be partitioned into subsets D0,D1,…,DkD0,D1,…,Dk such that D0=DD0=D and for any i∈{0,…,k−1}i∈{0,…,k−1}, each vertex vv in Di+1Di+1 has at least τ(v)τ(v) neighbors in D0∪…∪DiD0∪…∪Di. Dynamic monopolies are in fact modeling the irreversible spread of influence in social networks. In this paper we first obtain a lower bound for the smallest size of any dynamic monopoly in terms of the average threshold and the order of graph. Also we obtain an upper bound in terms of the minimum vertex cover of graphs. Then we derive the upper bound |G|/2|G|/2 for the smallest size of any dynamic monopoly when the graph GG contains at least one odd vertex, where the threshold of any vertex vv is set as ⌈(deg(v)+1)/2⌉⌈(deg(v)+1)/2⌉ (i.e. strict majority threshold). This bound improves the best known bound for strict majority threshold. We show that the latter bound can be achieved by a polynomial time algorithm. We also show that α′(G)+1α′(G)+1 is an upper bound for the size of strict majority dynamic monopoly, where α′(G)α′(G) stands for the matching number of GG. Finally, we obtain a basic upper bound for the smallest size of any dynamic monopoly, in terms of the average threshold and vertex degrees. Using this bound we derive some other upper bounds.