Dynamic monopolies in simple graphs | ||
| AUT Journal of Mathematics and Computing | ||
| مقاله 5، دوره 6، شماره 2، 2025، صفحه 151-162 اصل مقاله (470.42 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22060/ajmc.2024.22585.1178 | ||
| نویسندگان | ||
| Leila Musavizadeh Jazaeri؛ Leila Sharifan* | ||
| Department of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, Razavi Khorasan, Iran | ||
| چکیده | ||
| This 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 tiebreaking 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 dyn(G) for some special classes of graphs including paths, cycles and links of some graphs. | ||
| کلیدواژهها | ||
| Repetitive polling game؛ Dynamic monopoly؛ Vertex cover؛ Majority function | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 533 تعداد دریافت فایل اصل مقاله: 358 |
||
| تعداد نشریات | 9 |
| تعداد شمارهها | 455 |
| تعداد مقالات | 5,771 |
| تعداد مشاهده مقاله | 8,374,511 |
| تعداد دریافت فایل اصل مقاله | 6,932,569 |