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

DOI10.1016/J.IPL.2014.01.005MaRDI QIDQ2446567zbMATHOpenAlexFDO

Authors Yanyan Li

Publication date 17 April 2014

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

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

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)

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.

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

Cites work

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

Cited in

(2)

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

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)