Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433857 | Theoretical Computer Science | 2015 | 5 Pages |
Let G be any connected graph on n vertices, n≥2n≥2. Let k be any positive integer. Suppose that a fire breaks out at some vertex of G. Then, in each turn k firefighters can protect vertices of G — each can protect one vertex not yet on fire; Next the fire spreads to all unprotected neighbours.The k-surviving rate of G, denoted by ρk(G)ρk(G), is the expected fraction of vertices that can be saved from the fire by k firefighters, provided that the starting vertex is chosen uniformly at random. In this paper, it is shown that for any planar graph G we have ρ3(G)≥221. Moreover, 3 firefighters are needed for the first step only; after that it is enough to have 2 firefighters per each round. This result significantly improves the known solutions to a problem by Cai and Wang (there was no positive bound known for the surviving rate of general planar graph with only 3 firefighters). The proof is done using the separator theorem for planar graphs.