Contents

-

Firefighting on the Triangular Grid

Margaret-Ellen Messinger1
1Dalhousie University, Halifax, Nova Scotia, Canada

Abstract

A fire breaks out on a graph G and then f firefighters protect f vertices. At each subsequent interval, the fire spreads to all adjacent unprotected vertices, and firefighters protect f unburned vertices. Let fG be the minimum number of firefighters needed to contain a fire on graph G. If the triangular grid goes unprotected to time t=k when fG firefighters arrive and begin protecting vertices, the fire can be contained by time t=18k+3 with at most 172k2+58k+5 vertices burned.