On Dissemination Thresholds in Regular and Irregular Graph Classes
2009
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<\frac{1}{2}\)
. We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI