Firefighting on a random geometric graph1. Issue 3 (27th June 2013)

• Record Type: Journal Article
• Authors: Barghi, Amir; Winkler, Peter
• Is Part Of: Random structures & algorithms. Volume 46:Issue 3(2015)
• Page Start: 466
• Page End: 477
• Publication Date: 2013-06-27
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20511
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let<italic>G</italic>_{<italic>λ</italic>} be the graph whose vertices are points of a planar Poisson process of density <italic>λ</italic>, 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 <italic>f</italic> vertices can be deleted at each time‐step. Let <italic>f</italic>_{<italic>λ</italic>} be the least <italic>f</italic> such that, with probability 1, any fire on <italic>G</italic>_{<italic>λ</italic>} can be stopped in finite time. We show that <italic>f</italic>_{<italic>λ</italic>} is bounded between two linear functions of <italic>λ</italic>. 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</p> </abstract>