Tight bounds on the minimum size of a dynamic monopoly

DOI10.1007/978-3-030-13435-8_28zbMATH Open1425.05146arXiv1901.05917OpenAlexW2909014749MaRDI QIDQ2278293FDOQ2278293

Authors: Ahad N. Zehmakan 

Publication date: 4 December 2019

Abstract: Assume that you are given a graph $G=(V,E)$ with an initial coloring, where each node is black or white. Then, in discrete-time rounds all nodes simultaneously update their color following a predefined deterministic rule. This process is called two-way $r$-bootstrap percolation, for some integer $r$, if a node with at least $r$ black neighbors gets black and white otherwise. Similarly, in two-way $alpha$-bootstrap percolation, for some $0<alpha<1$, a node gets black if at least $alpha$ fraction of its neighbors are black, and white otherwise. The two aforementioned processes are called respectively $r$-bootstrap and $alpha$-bootstrap percolation if we require that a black node stays black forever. For each of these processes, we say a node set $D$ is a dynamic monopoly whenever the following holds: If all nodes in $D$ are black then the graph gets fully black eventually. We provide tight upper and lower bounds on the minimum size of a dynamic monopoly.

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

Recommendations

• Dynamic monopolies in two-way bootstrap percolation
• On the spread of influence in graphs
• Size bounds for dynamic monopolies
• Dynamic monopolies in tori.
• On dynamic monopolies of graphs: the average and strict majority thresholds

zbMATH Keywords

target set selectionbootstrap percolationthreshold modeldynamic monopolypercolating set

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Microeconomic theory (price theory and economic markets) (91B24)

Cited In (8)

• Dynamic monopolies of constant size
• On time versus size for monotone dynamic monopolies in regular topologies
• Title not available (Why is that?)
• Target set in threshold models
• Rumor spreading: A trigger for proliferation or fading away
• Deterministic bootstrap percolation on trees
• A new test for monopoly with limited cost data
• Threshold behavior of bootstrap percolation

This page was built for publication: Tight bounds on the minimum size of a dynamic monopoly

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