On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold

Khoshkhah, Kaveh ; Zaker, Manouchehr

Canadian mathematical bulletin, Tome 58 (2015) no. 2, pp. 306-316

Résumé

Let $G$ be a graph and let $\tau $ be an assignment of nonnegative integer thresholds to the vertices of $G$ . A subset of vertices, $D$ , is said to be a $\tau $ -dynamicmonopoly if $V\left( G \right)$ can be partitioned into subsets ${{D}_{0}},\,{{D}_{1}},\,\ldots \,,\,{{D}_{k}}$ such that ${{D}_{0}}\,=\,D$ and for any $i\,\in \,\left\{ 0,\,\ldots \,,\,k-1 \right\}$ , each vertex $v$ in ${{D}_{i+1}}$ has at least $\tau \left( v \right)$ neighbors in ${{D}_{0}}\cup \cdots \cup {{D}_{i}}$ . Denote the size of smallest $\tau $ -dynamic monopoly by $\text{dy}{{\text{n}}_{\tau }}\left( G \right)$ and the average of thresholds in $\tau $ by $\bar{\tau }$ . We show that the values of $\text{dy}{{\text{n}}_{\tau }}\left( G \right)$ over all assignments $\tau $ with the same average threshold is a continuous set of integers. For any positive number $t$ , denote the maximum $\text{dy}{{\text{n}}_{\tau }}\left( G \right)$ taken over all threshold assignments $\tau $ with $\bar{\tau }\,\le \,t$ , by $\text{Ldy}{{\text{n}}_{t}}\left( G \right)$ . In fact, $\text{Ldy}{{\text{n}}_{t}}\left( G \right)$ shows the worst-case value of a dynamicmonopoly when the average threshold is a given number $t$ . We investigate under what conditions on $t$ , there exists an upper bound for $\text{Ldy}{{\text{n}}_{t}}\left( G \right)$ of the form $c\left| G \right|$ , where $c\,<\,1$ . Next, we show that $\text{Ldy}{{\text{n}}_{t}}\left( G \right)$ is $\text{coNP}$ -hard for planar graphs but has polynomial-time solution for forests.

Détail

DOI : 10.4153/CMB-2015-021-4

Mots-clés : 05C69, 05C85, spread of influence in graphs, irreversible dynamic monopolies, target set selection

Bibliographie

[1] [1] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B., Network flows. Theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, NJ, 1993. Google Scholar

[2] [2] Bondy, J. A. and U.S.R. Murty, Graph theory. Graduate Texts in Mathematics, z, Springer, New York, 2008. Google Scholar

[3] [3] Chang, C-L. and Lyuu, Y-D., On irreversible dynamic monopolies in general graphs. arxiv:0904.2306v3 Google Scholar

[4] [4] Centeno, C. C., Dourado, M. C., Penso, L. D., Rautenbach, D., and Szwarcûter, J. L., Irreversible conversion of graphs. Theoret. Comput. Sci. 412(2011), no. 29, 3693–3700. Google Scholar | DOI

[5] [5] Centeno, C. C. and Rautenbach, D., Remarks on dynamic monopolies with given average thresholds. Discuss. Math. Graph Theory 35(2015), no. 1, 133-140. Google Scholar | DOI

[6] [6] Chen, N., On the approximability of influence in social networks. SIAM J. Discrete Math. 23(2009), no. 3. 1400–1415 Google Scholar | DOI

[7] [7] Dreyer, P. A., Jr. and Roberts, E S., Irreversible k-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl. Math. 157(2009), no. 7, 1615-1227. Google Scholar | DOI

[8] [8] Flocchini, P., Kralovic, R., Roncato, A., Ruzicka, P., and Santoro, N., On time versus size for monotone dynamic monopolies in regular topologies. J. Discrete Algorithms 1(2003), no. z, 129-150. Google Scholar | DOI

[9] [9] Garey, M. R. and Johnson, D. S., Computers and intractability. A guide to theory of NP-completeness. A Series of Books in the Mathematical Sciences, W. H. Freeman &amp; Co., San Franciso, CA, 1979. Google Scholar

[10] [10] Khoshkhah, K., Soltani, H., Zaker, M., On dynamic monopolies of graphs: The average and strict majority thresholds, Discrete Optim. 9 (2012) 77-83. Google Scholar | DOI

[11] [11] Soltani, H. and Zaker, M., Dynamic monopolies of graphs with probabilistic thresholds. Bull. Aust. Math. Soc. 90(2014), no. 3, 363-375. Google Scholar | DOI

[12] [12] Zaker, M., On dynamic monopolies of graphs with general thresholds. Discrete Math. 312(2012), no. 6, 1136–1143. Google Scholar | DOI

[13] [13] Zaker, M., Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs. Discrete Appl. Math. 161(2013), no. 16-17, 2716–2723. Google Scholar | DOI