05309961

j

05309961 Messinger, M.E. Average firefighting on infinite grids. Australas. J. Comb. 41, 15-28 (2008). 2008 Published for the Combinatorial Mathematics Society of Australasia by the Centre for Discrete Mathematics and Computing, the University of Queensland, Brisbane, QLD EN domination infinite grid Summary: In the Firefighter Problem, a fire breaks out at a vertex of a graph $G$, then $f$ firefighters protect $f$ vertices. At each subsequent time step, the fire spreads from each ``burned'' vertex to all of its unprotected neighbours, then $f$ firefighters "protect" / unburned vertices. Once a vertex is protected or burned, it remains so from then onward. A common objective is to determine the minimum number /, such that if / vertices are protected at each time step, then the fire can be contained on a graph G. In this paper, average firefighting is introduced: the number of vertices protected in each time step is allowed to vary. If the number of firefighters used is periodic and the average number (per time step) is strictly greater than 3/2, then a fire on the Cartesian grid can be contained. Similar results are also determined for the triangular and strong grids.