The surviving rate of planar graphs

AbstractLet G be a connected graph with n≥2 vertices. Let k≥1 be an integer. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects k-vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let snk(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate ρk(G) of G is defined to be ∑v∈V(G)snk(v)/n2, which is the average proportion of saved vertices.In this paper, we show that every planar graph G with minimum degree δ satisfies ρ4(G)>311 if δ=5, ρ4(G)>319 if δ=4, and ρ4(G)>19 if δ≤3. This improves a result in [W. Wang, S. Finbow, P. Wang, The surviving rate of an infected network, Theoret. Comput. Sci. 411 (2010) 3651–3660]