| Record |
| Author |
Kiwi, M.; de Espanes, P.M.; Rapaport, I.; Rica, S.; Theyssier, G. |
| Title |
Strict Majority Bootstrap Percolation in the r-wheel |
Type |
|
| Year |
2014 |
Publication |
Information Processing Letters |
Abbreviated Journal |
Inf. Process. Lett. |
| Volume |
114 |
Issue |
6 |
Pages |
277-281 |
| Keywords |
Bootstrap percolation; Interconnection networks |
| Abstract |
In the strict Majority Bootstrap Percolation process each passive vertex v becomes active if at least [deg(v)+1/2] of its neighbors are active (and thereafter never changes its state). We address the problem of finding graphs for which a small proportion of initial active vertices is likely to eventually make all vertices active. We study the problem on a ring of n vertices augmented with a “central” vertex u. Each vertex in the ring, besides being connected to u, is connected to its r closest neighbors to the left and to the right. We prove that if vertices are initially active with probability p > 1/4 then, for large values of r, percolation occurs with probability arbitrarily close to I as n -> infinity. Also, if p < 1/4, then the probability of percolation is bounded away from 1. (c) 2014 Elsevier B.V. All rights reserved. |
| Address |
[Kiwi, M.; de Espanes, P. Moisset; Rapaport, I.] Univ Chile, DIM, CMM, UMI 2807 CNRS, Santiago, Chile, Email: rapaport@dim.uchile.cl |
| Corporate Author |
|
Thesis |
|
| Publisher |
Elsevier Science Bv |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
Series Volume  |
|
Series Issue |
|
Edition |
|
| ISSN |
0020-0190 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000334485800001 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
370 |
| Permanent link to this record |
