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.
Dr. Shelley Stahl, Thesis Advisor
Dr. John Pike, Committee Member
Dr. Stephen Flood, Committee Member
Copyright and Permissions
Original document was submitted as an Honors Program requirement. Copyright is held by the author.
Days-Merrill, Sarah. (2019). Fireﬁghter Problem Played on Inﬁnite Graphs. In BSU Honors Program Theses and Projects. Item 364. Available at: https://vc.bridgew.edu/honors_proj/364
Copyright © 2019 Sarah Days-Merrill