Dynamic Monopolies of Constant Size
Dynamic Monopolies of Constant Size
复制标题
DOI：
10.1006/jctb.2001.2045
复制
发表时间：
1999-11
期刊：
影响因子：
--
通讯作者：
Eli Berger
中科院分区：
文献类型：
--
作者：
Eli Berger
该论文处理图表上的投票游戏。最初，每个顶点颜色为白色或黑色。在每个回合中，每个顶点都由附近大多数顶点共享的颜色，上一轮。 （所有重新加工都是同时完成的。）我们说，如果以W0彩色白色的顶点启动游戏，则顶点W0是一个动态的垄断或发电机，则整个系统是白色的，经过有限的回合。 D. Peleg（1998，离散应用Math.86，262？273）询问动态垄断可能是顶点数量的函数。我们证明答案是o（1）。
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 W0 of vertices is a dynamic monopoly or dynamo if starting the game with the vertices of W0 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).