Strict Majority Bootstrap Percolation in the r-wheel
Kiwi
M
author
de Espanes
P
M
author
Rapaport
I
author
Rica
S
author
Theyssier
G
author
2014
English
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.
Bootstrap percolation
Interconnection networks
WOS:000334485800001
exported from refbase (show.php?record=370), last updated on Sat, 31 May 2014 13:53:31 -0400
text
files/347_Kiwi_etal2014.pdf
10.1016/j.ipl.2014.01.005
Kiwi_etal2014
Information Processing Letters
Inf. Process. Lett.
2014
Elsevier Science Bv
continuing
periodical
academic journal
114
6
277
281
0020-0190