On Dissemination Thresholds in Regular and Irregular Graph Classes

On Dissemination Thresholds in Regular and Irregular Graph Classes

0.00 Avg rating0 Votes
Article ID: iaor20111263
Volume: 59
Issue: 1
Start Page Number: 16
End Page Number: 34
Publication Date: Jan 2011
Journal: Algorithmica
Authors: , , ,
Keywords: vertex cover
Abstract:

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 Unknown character 1 2 equ1 . We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.

Reviews

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