CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Publications        
Abstract view

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

  Published:2015-03-18
 Printed: Jun 2015
  • Kaveh Khoshkhah,
    Department of Mathematics, Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran
  • Manouchehr Zaker,
    Department of Mathematics, Institute for Advanced Studies in Basic Sciences, Zanjan 45137-66731, Iran
Format:   LaTeX   MathJax   PDF  

Abstract

Let $G$ be a graph and $\tau$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices, $D$ is said to be a $\tau$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, \ldots, D_k$ such that $D_0=D$ and for any $i\in \{0, \ldots, k-1\}$, each vertex $v$ in $D_{i+1}$ has at least $\tau(v)$ neighbors in $D_0\cup \ldots \cup D_i$. Denote the size of smallest $\tau$-dynamic monopoly by $dyn_{\tau}(G)$ and the average of thresholds in $\tau$ by $\overline{\tau}$. We show that the values of $dyn_{\tau}(G)$ over all assignments $\tau$ with the same average threshold is a continuous set of integers. For any positive number $t$, denote the maximum $dyn_{\tau}(G)$ taken over all threshold assignments $\tau$ with $\overline{\tau}\leq t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worst-case value of a dynamic monopoly when the average threshold is a given number $t$. We investigate under what conditions on $t$, there exists an upper bound for $Ldyn_{t}(G)$ of the form $c|G|$, where $c\lt 1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar graphs but has polynomial-time solution for forests.
Keywords: spread of influence in graphs, irreversible dynamic monopolies, target set selection spread of influence in graphs, irreversible dynamic monopolies, target set selection
MSC Classifications: 05C69, 05C85 show english descriptions Dominating sets, independent sets, cliques
Graph algorithms [See also 68R10, 68W05]
05C69 - Dominating sets, independent sets, cliques
05C85 - Graph algorithms [See also 68R10, 68W05]
 

© Canadian Mathematical Society, 2017 : https://cms.math.ca/