کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433857 | 689640 | 2015 | 5 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 593, 16 August 2015, Pages 160–164