Size bounds for dynamic monopolies

✍ Scribed by D. Peleg

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 614 KB
• Volume: 86
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00043-2

✦ Synopsis

This paper considers a repetitive polling game played on an n-vertex graph G. Initially, each vertex is colored black or white. At each round, each vertex (simultaneously) recolors itself by the color of the majority of its neighborhood. A set of vertices M is said to be a dynamic monopoly, abbreviated dynamo, if starting the game with the vertices of M colored white, the system eventually reaches an all-white global state. WC study the question of how small a dynamic monopoly might be in various models. In a number of these models we derive tight bounds of fl(fi) on the minimum size of monotone dynamos, namely, ones guaranteeing that throughout the game, a white vertex never turns black. In addition, in a number of these models we derive similar tight bounds (of 0(&))

on the minimum size of 2-round dynamos, namely, ones that lead to the all-white state in exactly two rounds. Finally, we make some observations concerning the existence of small "drawing sets", that lead to nearly-balanced final states.