Strict majority bootstrap percolation in the \textit{r}-wheel

DOI10.1016/J.IPL.2014.01.005zbMATH Open1284.68467arXiv1308.3831OpenAlexW2069174998MaRDI QIDQ2446567FDOQ2446567

Authors: Yanyan Li 

Publication date: 17 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: In this paper we study the strict majority bootstrap percolation process on graphs. Vertices may be active or passive. Initially, active vertices are chosen independently with probability p. Each passive vertex becomes active if at least half of its neighbors are active (and thereafter never changes its state). If at the end of the process all vertices become active then we say that the initial set of active vertices percolates on the graph. We address the problem of finding graphs for which percolation is likely to occur for small values of p. Specifically, we study a graph that we call r-wheel: a ring of n vertices augmented with a universal vertex where each vertex in the ring is connected to its r closest neighbors to the left and to its r closest neighbors to the right. We prove that the critical probability is 1/4. In other words, if p>1/4 then for large values of r percolation occurs with probability arbitrarily close to 1 as n goes to infinity. On the other hand, if p<1/4 then the probability of percolation is bounded away from 1.

Full work available at URL: https://arxiv.org/abs/1308.3831

Recommendations

• Majority bootstrap percolation on \(G(n,p)\)
• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• Majority Bootstrap Percolation on the Hypercube
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• Bootstrap percolation on the random regular graph
• Bootstrap percolation in random \(k\)-uniform hypergraphs
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on G(n,p) revisited
• \(K_{r,s}\) graph bootstrap percolation
• A sharp threshold for bootstrap percolation in a random hypergraph

zbMATH Keywords

interconnection networksbootstrap percolation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Cellular automata (computational aspects) (68Q80) Network design and communication in computer systems (68M10)

Cites Work

• On the enumeration and generation of generalized Dyck words
• The sharp threshold for bootstrap percolation in all dimensions
• Majority Bootstrap Percolation on the Hypercube
• On dissemination thresholds in regular and irregular graph classes
• Bootstrap percolation on the random regular graph

Cited In (2)

• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold

This page was built for publication: Strict majority bootstrap percolation in the \textit{r}-wheel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446567)