Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-25T04:01:21.929Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  20 November 2018

Kaveh Khoshkhah
Affiliation:
Department of Mathematics, Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran. e-mail: [email protected], e-mail: [email protected]
Manouchehr Zaker
Affiliation:
Department of Mathematics, Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran. e-mail: [email protected], e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 2015

References

[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] Bondy, J. A. and U.S.R. Murty, Graph theory. Graduate Texts in Mathematics, z, Springer, New York, 2008.Google Scholar
[3] Chang, C-L. and Lyuu, Y-D., On irreversible dynamic monopolies in general graphs. arxiv:0904.2306v3Google Scholar
[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, 36933700. http://dx.doi.org/10.1016/j.tcs.2011.03.029 Google Scholar
[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. http://dx.doi.org/10.71 51/dmgt.1788 Google Scholar
[6] Chen, N., On the approximability of influence in social networks. SIAM J. Discrete Math. 23(2009), no. 3. 14001415 http://dx.doi.org/10.1137/0807361 7X Google Scholar
[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. http://dx.doi.org/10.101 6/j.dam.2 008.09.012 Google Scholar
[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. http://dx.doi.org/10.1016/S1570-8667(03)00022-4 Google Scholar
[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 & Co., San Franciso, CA, 1979.Google Scholar
[10] Khoshkhah, K., Soltani, H., Zaker, M., On dynamic monopolies of graphs: The average and strict majority thresholds, Discrete Optim. 9 (2012) 77-83. http://dx.doi.org/10.101 6/j.disopt.2012.02.001 Google Scholar
[11] Soltani, H. and Zaker, M., Dynamic monopolies of graphs with probabilistic thresholds. Bull. Aust. Math. Soc. 90(2014), no. 3, 363-375. http://dx.doi.org/10.1017/S0004972 714000604 Google Scholar
[12] Zaker, M., On dynamic monopolies of graphs with general thresholds. Discrete Math. 312(2012), no. 6, 11361143. http://dx.doi.org/10.1016/j.disc.2011.11.038 Google Scholar
[13] Zaker, M., Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs. Discrete Appl. Math. 161(2013), no. 16-17, 27162723. http://dx.doi.org/10.1016/j.dam.2013.04.012 Google Scholar