On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold

摘要

Let G be a graph and let tau be an assignment of nonnegative integer thresholds to the vertices of G. A subset of vertices, D, is said to be a tau-dynamic monopoly if V(G) can be partitioned into subsets D-0,D-1,..., D-k such that D-0 = D and for any i is an element of {0,..., k-1}, each vertex v in Di+1 has at least tau(v) neighbors in D0U...UDi. Denote the size of smallest tau-dynamic monopoly by dyn(tau)(G) and the average of thresholds in tau by (tau) over bar. We show that the values of dyn(tau)(G) over all assignments tau with the same average threshold is a continuous set of integers. For any positive number t, denote the maximum dyn(tau)(G) taken over all threshold assignments tau with (tau) over tilde <= t, by Ldyn(t)(G). In fact, Ldyn(t)(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 Ldyn(t)(G) of the form c vertical bar G broken vertical bar, where c < 1. Next, we show that Ldyn(t)(G) is coNP-hard for planar graphs but has polynomial-time solution for forests.