\input zb-basic
\input zb-ioport
\iteman{io-port 06014309}
\itemau{Kong, Jiangxu; Wang, Weifan; Zhu, Xuding}
\itemti{The surviving rate of planar graphs.}
\itemso{Theor. Comput. Sci. 416, 65-70 (2012).}
\itemab
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 \le 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.
\itemrv{Dan S. Archdeacon (Burlington)}
\itemcc{}
\itemut{firefighting; surviving rate; planar graphs}
\itemli{doi:10.1016/j.tcs.2011.10.002}
\end