✦ LIBER ✦

Dynamic Monopolies of Constant Size

✍ Scribed by Eli Berger

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 168 KB
Volume: 83
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2045

No coin nor oath required. For personal study only.

✦ Synopsis

The paper deals with a polling game on a graph. Initially, each vertex is colored white or black. At each round, each vertex is colored by the color shared by the majority of vertices in its neighborhood, at the previous round. (All recolorings are done simultaneously.) We say that a set W 0 of vertices is a dynamic monopoly or dynamo if starting the game with the vertices of W 0 colored white, the entire system is white after a finite number of rounds. D. Peleg (1998, Discrete Appl. Math. 86, 262 273) asked how small a dynamic monopoly may be as a function of the number of vertices. We show that the answer is O(1).

📜 SIMILAR VOLUMES

Size bounds for dynamic monopolies

✍ D. Peleg 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 614 KB

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, abbrevia

Stability of the constant cost dynamic l

Stability of the constant cost dynamic lot size model

✍ Knut Richter 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 405 KB

Sequential stability of the constant cos

Sequential stability of the constant cost dynamic lot size model

✍ Knut Richter 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 376 KB

The stability region of the dynamic lot size problem understood as the set of cost parameter inputs for which an optimal solution remains valid has been studied in various papers of V6r6s and the author. Recently van Hoesel and Wagelmans discussed these results and suggested some numerical improveme

Sequential stability of the constant cos

Sequential stability of the constant cost dynamic lot size model-searching for monotonicity

✍ Knut Richter; Jens Weber 📂 Article 📅 1994 🏛 Springer 🌐 German ⚖ 638 KB

Consistency and optimality in a dynamic

Consistency and optimality in a dynamic game of pollution control II: Monopoly

✍ Amitrajeet A. Batabyal 📂 Article 📅 1996 🏛 Springer 🌐 English ⚖ 900 KB

Substituent and ring size dependence of

Substituent and ring size dependence of the coupling constant

✍ M. J. Collins; P. M. Hatton; S. Sternhell; C. W. Tansey 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB

The magnitude of the 45 proton-proton coupling constant across the fragment CH3-C-C-H (a probe of the bond order between the central spz-sp2 hybridized carbon atoms) has been found to be essentially independent of substitution on a toluene fragment and on the size of the ring containing the ortho-al