# Fireﬁghter Problem Played on Inﬁnite Graphs

5-6-2019

Thesis

## Abstract

The Firefighter Problem was introduced over 30 years ago and continues to be studied by researchers today. The problem consists of a graph of interest where a fire breaks out at time t = 0 on any given vertex of thegraph G. The player, then, gets to place a firefighter to “protect” a vertex from the fire. Each consecutive turn,the fire spreads to adjacent vertices. These vertices are then referred to as “burned”. The firefighter also gets tomove to protect an additional, unburned vertex, completing the first round. Each vertex that the firefighter “defends” stays protected for the remainder of the game. The game ends when the fire cannot move to anyadjacent vertices. This game can be used to solve real world problems. For example, we can model the spread ofdiseases in a community or the spread of a wildfire using the Firefighter Problem. There are many known resultsfor the Firefighter Problem on finite graphs. In this project, we study the Firefighter Problem on infinitegraphs, with the goal of expanding on known results. We are exploring various infinite grids by imposing the additional requirement that firefighters can only move to adjacent, unburned vertices.

Mathematics

## Thesis Comittee

Dr. John Pike, Committee Member

Dr. Stephen Flood, Committee Member