Dynamic monopolies in simple graphs

Document Type : Original Article

Authors

Department of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, Razavi Khorasan, Iran

Abstract

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.

Keywords

Main Subjects


[1] E. Ackerman, O. Ben-Zwi, and G. Wolfovitz, Combinatorial model and bounds for target set selection,
Theoret. Comput. Sci., 411 (2010), pp. 4017–4022.
[2] R. C. Brigham, R. D. Dutton, T. W. Haynes, and S. T. Hedetniemi, Powerful alliances in graphs,
Discrete Math., 309 (2009), pp. 2140–2147.
[3] S. Brunetti, G. Cordasco, L. Gargano, E. Lodi, and W. Quattrociocchi, Minimum weight dynamo
and fast opinion spreading (extended abstract), in Graph-theoretic concepts in computer science, vol. 7551 of
Lecture Notes in Comput. Sci., Springer, Heidelberg, 2012, pp. 249–261.
[4] C. C. Centeno, M. C. Dourado, L. D. Penso, D. Rautenbach, and J. L. Szwarcfiter, Irreversible
conversion of graphs, Theoret. Comput. Sci., 412 (2011), pp. 3693–3700.
[5] M. C. Dourado, L. D. Penso, D. Rautenbach, and J. L. Szwarcfiter, Reversible iterative graph
processes, Theoret. Comput. Sci., 460 (2012), pp. 16–25.
[6] M. Fazli, On dynamic monopolies of cubic graphs, The CSI Journal on Computer Science and Engineering,
15 (2017), pp. 39–44.
[7] M. Fazli, M. Ghodsi, J. Habibi, P. Jalaly, V. Mirrokni, and S. Sadeghian, On non-progressive spread
of influence through social networks, Theoret. Comput. Sci., 550 (2014), pp. 36–50.
[8] P. Flocchini, R. Kralovi ´ c, P. Ru ˇ ˇzicka, A. Roncato, and N. Santoro ˇ , On time versus size for
monotone dynamic monopolies in regular topologies, vol. 1, 2003, pp. 129–150. SIROCCO 2000 (L’Aquila).
[9] P. Flocchini, E. Lodi, F. Luccio, L. Pagli, and N. Santoro, Dynamic monopolies in tori, vol. 137, 2004,
pp. 197–212. 1st International Workshop on Algorithms, Combinatorics, and Optimization in Interconnection
Networks (IWACOIN ’99).
[10] E. Goles and J. Olivos, Periodic behaviour of generalized threshold functions, Discrete Math., 30 (1980),
pp. 187–189.
[11] E. Goles and M. Tchuente, Iterative behaviour of generalized majority functions, Math. Social Sci., 4
(1983), pp. 197–204.
[12] A. Harutyunyan, Some bounds on global alliances in trees, Discrete Appl. Math., 161 (2013), pp. 1739–1746.
[13] L. M. Jazaeri, L. Sharifan, and A. Barzanouni, Periodic structure of repetitive polling game on graphs.
submitted.
[14] C. Jeger and A. N. Zehmakan, Dynamic monopolies in two-way bootstrap percolation, Discrete Appl.
Math., 262 (2019), pp. 116–126.
[15] K. Khoshkhah, H. Soltani, and M. Zaker, On dynamic monopolies of graphs: the average and strict
majority thresholds, Discrete Optim., 9 (2012), pp. 77–83.
[16] A. Mizrachi, Majority vote and monopolies in social networks, Master’s thesis, Ben-Gurion University of the
Negev, 2013.
[17] D. Peleg, Size bounds for dynamic monopolies, Discrete Appl. Math., 86 (1998), pp. 263–273.
[18] D. Peleg, Local majorities, coalitions and monopolies in graphs: a review, vol. 282, 2002, pp. 231–257. FUN
with algorithms (Elba, 1998).
[19] D. Reichman, New bounds for contagious sets, Discrete Math., 312 (2012), pp. 1812–1814.
[20] R. H. Schonmann, Finite size scaling behavior of a biased majority rule cellular automaton, Phys. A, 167
(1990), pp. 619–627.
[21] H. Soltani and M. Zaker, On dynamic monopolies of graphs with probabilistic thresholds, Bull. Aust. Math.
Soc., 90 (2014), pp. 363–375.
[22] A. N. Zehmakan, Tight bounds on the minimum size of a dynamic monopoly, in Language and automata
theory and applications, vol. 11417 of Lecture Notes in Comput. Sci., Springer, Cham, 2019, pp. 381–393.