The surviving rate of planar graphs (Q764317)

This paper considers firefighting on graphs. Given a graph \(G\) suppose that a fire breaks out at vertex \(v\). At each step the firefighters can protect \(k\) vertices, after which the fire spreads to any unprotected vertex adjacent to a vertex already on fire. The firefighters' goal is to maximize the number of saved vertices, that is, the number of vertices remaining unburned after the fire no longer spreads. Let \(sn_k(v)\) be the maximum number of vertices in \(G\) that can be saved when a fire breaks out at \(v \in V(G)\). The \(k\)-surviving rate of \(G\) is \(\rho_k(G) = \sum_{v \in V(G)} sn_k(G)/n^2\). This represents the average proportion of saved vertices over all possible starting vertices. The authors focus on the \(4\)-surviving rate of planar graphs. Let \(\delta\) denote the minimum degree of \(G\). They show \(\rho_4 (G) > 1/9\) for \(\delta \leq 3\), \(\rho_4 (G) > 3/19\) for \(\delta = 4\), and \(\rho_4(G) > 3/11\) for \(\delta = 5\). It follows that \(\rho_4(G)\) is bounded away from 0 for any planar \(G\). The proof uses discharging techniques based on Euler's formula to find suitable small configurations.