Firefighting on Geometric Graphs with Density Bounds

被引:0
作者
Barghi, Amir [1 ]
Winkler, Peter [2 ]
机构
[1] State Univ New York New Paltz, Dept Math, New Paltz, NY 12561 USA
[2] Dartmouth, Dept Math, Hanover, NH 03755 USA
关键词
firefighting; geometric graph;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 A vertices, then f (G) is bounded above by the ceiling of a universal constant times 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 K vertices, then f(G) is bounded below by K times the square of the floor of a universal constant times 1/r.
引用
收藏
页码:63 / 86
页数:24
相关论文
共 8 条
  • [1] [Anonymous], THESIS
  • [2] [Anonymous], 1995, P 25 MAN C COMB MATH
  • [3] Barghi A., 2011, THESIS
  • [4] Bonato A., 2011, The Game of Cops and Robbers on Graphs
  • [5] Finbow S, 2009, AUSTRALAS J COMB, V43, P57
  • [6] Matousek Jiri, 2013, Graduate Texts in Mathematics, V212
  • [7] Messinger M. -E., 2004, THESIS
  • [8] MOELLER SA, 2002, J COMBIN MATH COMBIN, V41, P19