2016/01/09 by Michael Gentner, Dieter Rautenbach, Gentner, Michael +1
Computer Science · Decision Sciences · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #FOS: Mathematics #Game Theory and Applications #math.CO
paper · pdf · doi:10.48550/arxiv.1601.02099
openalex publication_date 2016/01/09 · arxiv created 2016/02/15 · arxiv updated 2016/02/16 · openalex created_date 2022/09/28 · openalex updated_date 2026/07/28
Let G be a graph, and let ρ∈ (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 ρdG(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↦ \lceil ρdG(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 \frac1ρ, Chang (Triggering cascades on undirected connected graphs, Information Processing Letters 111 (2011) 973-978) showed hρ(G)≤ 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)≤ 4.92ρn(G). We show that for every ε>0, there is some ρ(ε)>0 such that hρ(G) ≤(2+ε)ρn(G) for every ρ in (0,ρ(ε)), and every connected graph G that has maximum degree at least \frac1ρ and girth at least 5. Furthermore, we show that hρ(T) ≤ ρn(T) for every ρ in (0,1], and every tree T that has order at least \frac1ρ.