Firefighting on a random geometric graph1. Issue 3 (27th June 2013) - Barghi, Amir; Winkler, Peter
Abstract LetGλ be the graph whose vertices are points of a planar Poisson process of density λ, with vertices adjacent if they are within distance 1. A "fire" begins at some vertex and spreads to all neighbors in discrete steps; in the meantime f vertices can be deleted at each time‐step. Let fλ be the least f such that, with probability 1, any fire on Gλ can be stopped in finite time. We show that fλ is bounded between two linear functions of λ. The lower bound makes use of a new result concerning oriented percolation in the plane; the constant factor in the upper bound is is tight, provided a certain conjecture, for which we offer supporting evidence, is correct. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 466–477, 2015