
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.
firefighting, Planar graphs, Surviving rate, Enumeration in graph theory, planar graphs, Planar graphs; geometric and topological aspects of graph theory, Theoretical Computer Science, surviving rate, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Firefighter problem, Computer Science(all)
firefighting, Planar graphs, Surviving rate, Enumeration in graph theory, planar graphs, Planar graphs; geometric and topological aspects of graph theory, Theoretical Computer Science, surviving rate, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Firefighter problem, Computer Science(all)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 23 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
