|   | 
Author (up) 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