Tight Bounds on the Minimum Size of a Dynamic Monopoly

摘要

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 α-bootstrap percolation, for some 0 < α < 1, a node gets black if at least α fraction of its neighbors are black, and white otherwise. The two aforementioned processes are called respectively r-bootstrap and α-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.