Firefighting on Geometric Graphs with Density Bounds

Abstract

Let \(G\) be an infinite geometric graph; in particular, a graph whose vertices are a countable discrete set of points on the plane, with vertices \(u, v\) adjacent if their Euclidean distance is less than 1. A “fire” begins at some finite set of vertices and spreads to all neighbors in discrete steps; in the meantime, \(f\) vertices can be deleted at each time-step. Let \(f(G)\) be the least \(f\) for which any fire on \(G\) can be stopped in finite time. We show that if \(G\) has bounded density, in the sense that no open disk of radius \(r\) contains more than \(\lambda\) vertices, then \(f(G)\) is bounded above by ceiling of a universal constant times \(\frac{\lambda}{r^2}\). Similarly, if the density of \(G\) is bounded from below in the sense that every open disk of radius \(r\) contains at least \(\beta\) vertices, then \(f(G)\) is bounded below by \(\kappa\) times the square of the floor of a universal constant times \(\frac{1}{r}\).