Triggering cascades on strongly connected directed graphs

Consider the following process of activation on a strongly connected directed graph G ( V , E ) with threshold function ? : V ? N . In round zero, a set of vertices, called the seeds, are active. Thereafter, a vertex v ? V is activated in a round if it has at least ? ( v ) active in-neighbors in the previous round. Once a vertex is activated, it remains active. Sets of seeds activating all vertices after a finite number of rounds are known in the literature as irreversible dynamic monopolies (a.k.a. perfect target sets) corresponding to ( G , ? ) . With ? ( v ) = ? ? deg - ( v ) ? for all v ? V , where deg - ( v ) denotes the indegree of v and ? ? ( 0 , 1 ] , this paper proves the existence of an irreversible dynamic monopoly of size no more than max ? { 4.92 ? | V | , 1 } .