Dynamic Monopolies for Degree Proportional Thresholds in Connected Graphs of Girth at least Five and Trees

Dieter Rautenbach

Published 2016-01-09Version 1

Let $G$ be a graph, and let $\rho\in (0,1)$. For a set $D$ of vertices of $G$, let the set $H_{\rho}(D)$ arise by starting with the set $D$, and iteratively adding further vertices $u$ to the current set if they have at least $\lceil \rho d_G(u)\rceil$ neighbors in it. If $H_{\rho}(D)$ contains all vertices of $G$, then $D$ is known as an irreversible dynamic monopoly or a perfect target set associated with the threshold function $u\mapsto \lceil \rho d_G(u)\rceil$. Let $h_{\rho}(G)$ be the minimum cardinality of such an irreversible dynamic monopoly. For a connected graph $G$ of maximum degree at least $\frac{1}{\rho}$, Chang (Triggering cascades on undirected connected graphs, Information Processing Letters 111 (2011) 973-978) showed $h_{\rho}(G)\leq 5.83\rho n(G)$, which was improved by Chang and Lyuu (Triggering cascades on strongly connected directed graphs, Theoretical Computer Science 593 (2015) 62-69) to $h_{\rho}(G)\leq 4.92\rho n(G)$. We show that for every $\epsilon>0$, there is some $\rho(\epsilon)>0$ such that $h_{\rho}(G) \leq(2+\epsilon)\rho n(G)$ for every $\rho$ in $(0,\rho(\epsilon))$, and every connected graph $G$ that has maximum degree at least $\frac{1}{\rho}$ and girth at least $5$. Furthermore, we show that $h_{\rho}(T) \leq \frac{2\rho}{1+\rho}n(T)$ for every $\rho$ in $(0,1]$, and every tree $T$ that has maximum degree at least $\frac{1}{\rho}$.