Structural properties and surviving rate of planar graphs
Jiangxu Kong, Lianzhu Zhang, Weifan Wang · Discrete Mathematics Algorithms and Applications · 2014
Let G be a connected graph. Suppose that a fire breaks out at some vertex. 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. The k-surviving rate ρk(G) of G is the average proportion of saved vertices, if the starting vertex of the fire is chosen uniformly at random. A graph G is called k-good if there is a constant c > 0 such that ρk(G) ≥ c. We study structural properties of planar graphs and show that planar graphs are 3-good.