Article ID Journal Published Year Pages File Type
433857 Theoretical Computer Science 2015 5 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,