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

Abstract

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)\le 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)\le 4.92\rho n(G)$. We show that for every $\epsilon >0$, there is some $\rho (\epsilon )>0$ such that $h_{\rho }(G)\le (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)\le \rho n(T)$ for every $\rho$ in $(0,1]$, and every tree $T$ that has order at least $\frac{1}{\rho }$.