| |
Record |
Links |
|
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 |
