The surviving rate of an infected network
Let G be a connected network. Let k >= 1 be an integer. Suppose that a vertex upsilon of G becomes infected. A program is then installed on k-nodes not yet infected. Afterwards, the virus spreads to all its unprotected neighbors in each time interval. The virus and the network administrator take turns until the virus can no longer spread further. Let sn(k)(upsilon) denote the maximum number of vertices in G the network administrator can save when a virus infects upsilon. The k-surviving rate rho(k)(G) of G is defined to be the average value Sigma(upsilon is an element of V(G))sn(k)(upsilon)/n(2). In particular, we write rho(G) = rho(1)(G). In this paper, we first use a probabilistic method to show that almost all networks have k-surviving rate arbitrarily close to 0. Then, we prove the following results: (1) rho(G) >= 2/35 for a planar network G of girth at least 9; (2) rho(2)(G) >= 1/16 for a series-parallel network G; and (3) rho(2d-1)(G) >= 2/5d for a d-degenerate network G. (C) 2010 Elsevier B.V. All rights reserved.
surviving rate firefighter problem planar graph k(4)-minor free graph degenerate graph