Triggering cascades on strongly connected directed graphs
Journal
Theoretical Computer Science
Journal Volume
593
Pages
62-69
Date Issued
2015
Author(s)
Chang, C.-L.
Abstract
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}.
Type
journal article