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

Let $G$ be a graph, and let $ρ\in (0,1)$. For a set $D$ of vertices of $G$, let the set $H_ρ(D)$ arise by starting with the set $D$, and iteratively adding further vertices $u$ to the current set if they have at least $\lceil ρd_G(u)\rceil$ neighbors in it. If $H_ρ(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 ρd_G(u)\rceil$. Let $h_ρ(G)$ be the minimum cardinality of such an irreversible dynamic monopoly. For a connected graph $G$ of maximum degree at least $\frac{1}ρ$, Chang (Triggering cascades on undirected connected graphs, Information Processing Letters 111 (2011) 973-978) showed $h_ρ(G)\leq 5.83ρ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_ρ(G)\leq 4.92ρn(G)$. We show that for every $ε>0$, there is some $ρ(ε)>0$ such that $h_ρ(G) \leq(2+ε)ρn(G)$ for every $ρ$ in $(0,ρ(ε))$, and every connected graph $G$ that has maximum degree at least $\frac{1}ρ$ and girth at least $5$. Furthermore, we show that $h_ρ(T) \leq ρn(T)$ for every $ρ$ in $(0,1]$, and every tree $T$ that has order at least $\frac{1}ρ$.

No reviews yet.

No comments yet.