On Minimizing the Effects of Fire or a Virus on a Network.

The following problem was introduced at a conference in 1995. Fires start at \(F\) nodes of a graph and \(D\) defenders (firefighters) then protect \(D\) nodes not yet on fire. Then the fires spread to any neighbouring unprotected nodes. The fires and the firefighters take turns until the fires can no longer spread. We examine two cases: when the fires erupt at random and when they start at a set of nodes which allows the fires to maximize the damage. In the random situation, for a given number of nodes, we characterize the graphs which minimize the damage when \(D = F = 1\) and we show that the Star is an optimal graph for \(D = 1\) regardless of the value of \(F\). In the latter case, optimal graphs are given whenever \(D\) is at least as large as \(F\).