Premium
Firefighting on a random geometric graph
Author(s) -
Barghi Amir,
Winkler Peter
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20511
Subject(s) - vertex (graph theory) , combinatorics , upper and lower bounds , bounded function , conjecture , planar graph , mathematics , graph , percolation (cognitive psychology) , random graph , poisson point process , poisson distribution , discrete mathematics , mathematical analysis , statistics , neuroscience , biology
Let G λ 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