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 \( f_G \) 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 \( f_G \) firefighters arrive and begin protecting vertices, the fire can be contained by time \( t = 18k + 3 \) with at most \( 172k^2 + 58k + 5 \) vertices burned.