Amirkabir University of TechnologyAUT Journal of Mathematics and Computing2783-2449Articles in Press20240126Dynamic monopolies in simple graphs535010.22060/ajmc.2024.22585.1178ENLeilaMusavizadeh JazaeriHakim Sabzevari University, Sabzevar, IranLeilaSharifanFaculty of mathematics and computer science,
Hakim Sabzevari University
Sabzevar, IranJournal Article20230727This paper studies a repetitive polling game played on an $n$-vertex graph $G$. At first, each vertex is colored, Black or White. At each round, each vertex (simultaneously) recolors itself by the color of the majority of its closed neighborhood. The variants of the model differ in the choice of a particular tie-breaking rule. We assume the tie-breaking rule is Prefer-White and we study the relation between the notion of ``dynamic monopoly" and ``vertex cover" of $G$. In particular, we show that any vertex cover of $G$ is a dynamic monopoly or reaches a $2-$periodic coloring. Moreover, we compute $\rm{dyn}(G)$ for some special classes of graphs including paths, cycles and links of some graphs.