Dynamic monopolies in simple graphs
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 p...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Amirkabir University of Technology
2025-02-01
|
| Series: | AUT Journal of Mathematics and Computing |
| Subjects: | |
| Online Access: | https://ajmc.aut.ac.ir/article_5350_2bb6c5d854497148d55a2f5aeaa8486f.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823858266775486464 |
|---|---|
| author | Leila Musavizadeh Jazaeri Leila Sharifan |
| author_facet | Leila Musavizadeh Jazaeri Leila Sharifan |
| author_sort | Leila Musavizadeh Jazaeri |
| collection | DOAJ |
| description | 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 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}. |
| format | Article |
| id | doaj-art-62091814752b47f5bc0db7dd59120afa |
| institution | Kabale University |
| issn | 2783-2449 2783-2287 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | Amirkabir University of Technology |
| record_format | Article |
| series | AUT Journal of Mathematics and Computing |
| spelling | doaj-art-62091814752b47f5bc0db7dd59120afa2025-02-11T12:37:04ZengAmirkabir University of TechnologyAUT Journal of Mathematics and Computing2783-24492783-22872025-02-016215116210.22060/ajmc.2024.22585.11785350Dynamic monopolies in simple graphsLeila Musavizadeh Jazaeri0Leila Sharifan1Department of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, Razavi Khorasan, IranDepartment of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, Razavi Khorasan, IranThis 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}.https://ajmc.aut.ac.ir/article_5350_2bb6c5d854497148d55a2f5aeaa8486f.pdfrepetitive polling gamedynamic monopolyvertex covermajority function |
| spellingShingle | Leila Musavizadeh Jazaeri Leila Sharifan Dynamic monopolies in simple graphs AUT Journal of Mathematics and Computing repetitive polling game dynamic monopoly vertex cover majority function |
| title | Dynamic monopolies in simple graphs |
| title_full | Dynamic monopolies in simple graphs |
| title_fullStr | Dynamic monopolies in simple graphs |
| title_full_unstemmed | Dynamic monopolies in simple graphs |
| title_short | Dynamic monopolies in simple graphs |
| title_sort | dynamic monopolies in simple graphs |
| topic | repetitive polling game dynamic monopoly vertex cover majority function |
| url | https://ajmc.aut.ac.ir/article_5350_2bb6c5d854497148d55a2f5aeaa8486f.pdf |
| work_keys_str_mv | AT leilamusavizadehjazaeri dynamicmonopoliesinsimplegraphs AT leilasharifan dynamicmonopoliesinsimplegraphs |