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

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

0.00 Avg rating0 Votes
Article ID: iaor20124025
Volume: 9
Issue: 2
Start Page Number: 77
End Page Number: 83
Publication Date: May 2012
Journal: Discrete Optimization
Authors: , ,
Keywords: optimization
Abstract:

Let G equ1 be a graph and τ : V ( G ) N { 0 } equ2 be an assignment of thresholds to the vertices of G equ3. A subset of vertices D equ4 is said to be a dynamic monopoly corresponding to ( G , t ) equ5 if the vertices of G equ6 can be partitioned into subsets D 0 , D 1 , , D k equ7 such that D 0 = D equ8 and for any i { 0 , , k 1 } equ9, each vertex v equ10 in D i + 1 equ11 has at least t ( v ) equ12 neighbors in D 0 D i equ13. 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 equ14 for the smallest size of any dynamic monopoly when the graph G equ15 contains at least one odd vertex, where the threshold of any vertex v equ16 is set as ( d e g ( v ) + 1 ) / 2 equ17 (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 a ' ( G ) + 1 equ18 is an upper bound for the size of strict majority dynamic monopoly, where a ' ( G ) equ19 stands for the matching number of G equ20. 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.

Reviews

Required fields are marked *. Your email address will not be published.