New bounds for contagious sets

DOI10.1016/j.disc.2012.01.016zbMath1242.05265OpenAlexW1999279606MaRDI QIDQ418891

Daniel Reichman

Publication date: 30 May 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2012.01.016

zbMATH Keywords

bootstrap percolation\(d\)-degenerate graphs

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graph theory (05C99) Vertex degrees (05C07)

Related Items (20)

Deterministic bootstrap percolation on trees ⋮ Hardness Results for Seeding Complex Contagion with Neighborhoods ⋮ Contagious sets in dense graphs ⋮ Minimum degree conditions for small percolating sets in bootstrap percolation ⋮ A note on the acquaintance time of random graphs ⋮ Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives ⋮ New ordering methods to construct contagious sets and induced degenerate subgraphs ⋮ Hierarchical cycle-tree packing model for optimal \(K\)-core attack ⋮ Triggering cascades on strongly connected directed graphs ⋮ Recoverable Values for Independent Sets ⋮ Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees ⋮ Constant thresholds can make target set selection tractable ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ Acquaintance Time of Random Graphs Near Connectivity Threshold ⋮ Infinite and Giant Components in the Layers Percolation Model ⋮ On giant components and treewidth in the layers model ⋮ On the spread of influence in graphs ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ The acquaintance time of (percolated) random geometric graphs ⋮ Minimal contagious sets in random regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial model and bounds for target set selection
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the hypercube
• Bootstrap percolation in three dimensions
• On the size of identifying codes in binary hypercubes
• Large induced degenerate subgraphs
• Lower bounds on the independence number in terms of the degrees
• Recoverable Values for Independent Sets
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the random regular graph
• Majority Bootstrap Percolation on the Hypercube
• On the Approximability of Influence in Social Networks
• Random disease on the square grid
• The sharp threshold for bootstrap percolation in all dimensions

This page was built for publication: New bounds for contagious sets