Menu
Let \(G = (V, E)\) be a connected undirected graph. Suppose a fire breaks out at a vertex of \(G\) and spreads to all its unprotected neighbours in each time interval. Also, one vertex can be protected in each time interval. We are interested in the number of vertices that can be “saved”, that is, which will never be burned. An algorithm is presented to find the optimal solution in the 2-dimensional grid graphs and 3-dimensional cubic graphs. We also determined the upper and lower bounds of the maximum number of vertices that can be saved on the large product graphs. The problem of containing the fire with one firefighter or more is also considered.