caa a22 4500 445804726 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00453-009-9309-0 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9309-0 On Dissemination Thresholds in Regular and Irregular Graph Classes [Elektronische Daten] [I. Rapaport, K. Suchan, I. Todinca, J. Verstraete] 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 ofp. The Author(s), 2009 Bootstrap percolation nationallicence Cubic graphs nationallicence Information dissemination nationallicence Rapaport I. Departamento de Ingeniería Matemática and Centro de Modelamiento Matemático, Universidad de Chile, Santiago, Chile aut Suchan K. Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibañez, Santiago, Chile aut Todinca I. LIFO, Université d'Orléans, Orléans, France aut Verstraete J. University of California, San Diego, CA, USA aut Algorithmica Springer-Verlag 59/1(2011-01-01), 16-34 0178-4617 59:1<16 2011 59 453 https://doi.org/10.1007/s00453-009-9309-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9309-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Rapaport I. Departamento de Ingeniería Matemática and Centro de Modelamiento Matemático, Universidad de Chile, Santiago, Chile aut NATIONALLICENCE 700 1- Suchan K. Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibañez, Santiago, Chile aut NATIONALLICENCE 700 1- Todinca I. LIFO, Université d'Orléans, Orléans, France aut NATIONALLICENCE 700 1- Verstraete J. University of California, San Diego, CA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/1(2011-01-01), 16-34 0178-4617 59:1<16 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer