2014/05/23 by Kaveh Khoshkhah, Khoshkhah, Kaveh, Manouchehr Zaker +1
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Game Theory and Applications #Limits and Structures in Graph Theory #math.CO #msc:05C69 #msc:05C85 #msc:91D30
paper · pdf · doi:10.48550/arxiv.1405.6138
arxiv created 2014/05/23 · arxiv updated 2014/05/26
Let G be a graph and τ be an assignment of nonnegative integer thresholds to the vertices of G. A subset of vertices D is said to be a τ-dynamic monopoly, if V(G) can be partitioned into subsets D0, D1, …, Dk such that D0=D and for any i∈ \0, …, k-1\, each vertex v in Di+1 has at least τ(v) neighbors in D0∪ … ∪ Di. Denote the size of smallest τ-dynamic monopoly by dynτ(G) and the average of thresholds in τ by τ. We show that the values of dynτ(G) over all assignments τ with the same average threshold is a continuous set of integers. For any positive number t, denote the maximum dynτ(G) taken over all threshold assignments τ with τ≤ t, by Ldynt(G). In fact, Ldynt(G) shows the worst-case value of a dynamic monopoly when the average threshold is a given number t. We investigate under what conditions on t, there exists an upper bound for Ldynt(G) of the form c|G|, where c<1. Next, we show that Ldynt(G) is coNP-hard for planar graphs but has polynomial-time solution for forests.