The surviving rate of an outerplanar graph for the firefighter problem

Let 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 neighbour 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 , which is the average proportion of saved vertices.In this paper, we investigate the surviving rate of outerplanar graphs G with n≥2 vertices. The main results are as follows: (1) limn→∞ρ5(G)=1; and (2) if n≥8, and if n≥2, which improves the result in [L.Cai, W.Wang, The surviving rate of a graph for the firefighter problem, SIAM J. Discrete Math. 23 (2009) 1814–1826].