On Dissemination Thresholds in Regular and Irregular Graph Classes
Rapaport
I
author
Suchan
K
author
Todinca
I
author
Verstraete
J
author
2011
English
We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if p < 1/2. We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.
Bootstrap percolation
Cubic graphs
Information dissemination
WOS:000286525300003
exported from refbase (show.php?record=119), last updated on Sun, 27 Feb 2011 22:29:38 -0300
text
files/48_Rapaport_etal2011.pdf
10.1007/s00453-009-9309-0
Rapaport_etal2011
Algorithmica
Algorithmica
2011
Springer
continuing
periodical
academic journal
59
1
16
34
0178-4617