Abstract
In this paper, we consider the firefighter problem on a graph G = (V, E) that is either finite or infinite. Suppose that a fire breaks out at a given vertex v is an element of V.
In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible (if G is finite) or to stop the fire from spreading (for an infinite case).
The surviving rate rho(G) of a finite graph G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a vertex of G that is selected uniformly random. For a finite square grid P-n square P-n, we show that 5/8 + 0(1) {= rho(P-n square P-n) {= 67 243/105 300 + 0(1) (leaving the gap smaller than 0.0136) and conjecture that the surviving rate is asymptotic to 5/8.
We define the surviving rate for infinite graphs and prove it to be 1/4 for the infinite square grid, even for more than one (but finitely many) initial fires. For the infinite hexagonal grid we provide a winning strategy if two additional vertices can be protected at any point of the process, and we conjecture that the firefighter has no strategy to stop the fire without additional help.
We also show how the speed of the spreading fire can be reduced by a constant multiplicative factor. For triangular grid, we show that two firefighters can slow down the fire in the same sense, which is relevant to the conjecture that two firefighters cannot contain the fire on the triangular grid, and also corrects a previous result of Fogarty (2003). (C) 2014 Elsevier B.V.
All rights reserved.