Project Description

We start with a rooted graph (G, r) and an integer-valued function f(t). At time 0, r is set on fire. At the beginning of each subsequent time period, (t=1,2,3,...) we place f(t) firefighters on unburnt vertices. After we have placed the firefighters, any vertex adjacent to the fire that lacks a firefighter will then catch on fire. This process continues until the fire can no longer spread (all burnt vertices are adjacent only to burnt vertices or vertices with a firefighter). In an infinite graph, however, such as the infinite grid graph, it may be impossible to reach this stage. Wang and Moeller [1] proved that if f(t)=1, the fire cannot be contained on the infinite grid. Fogarty [2] proved that if f(t)=2, the fire can be contained within a finite number of time periods, even if the fire starts at multiple vertices. My advisor, Dr. Kah Loon Ng (with P. Raff, forthcoming), has proved that if f(t) is a periodic function with period p, and >1.5, then a fire that starts at a finite number of vertices can be contained in a finite amount of time. This summer, I will attempt to prove a conjecture by Ng and Raff, namely that if f(t) is the periodic function 2,1,2,1,..., then the fire cannot be contained on the infinite grid graph. This would prove that =1.5 does not guarantee that the fire can be contained, showing that the bound found by Ng and Raff is tight. I will also explore the firefighter problem on the infinite triangle graph, where each vertex has degree 6.

References