A variation on the firefighter problem on graphs

Marcoux, John (2022) A variation on the firefighter problem on graphs. Masters thesis, Memorial University of Newfoundland.

[img] [English] PDF - Accepted Version
Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.

Download (874kB)


In the classic version of the game of Firefighter, on the first turn a fire breaks out on a vertex in a graph G and then k firefighters protect k vertices. On each subsequent turn, the fire spreads to the collective unburnt neighbourhood of all the burning vertices and the firefighters again protect k vertices. Once a vertex has been burnt or protected it remains that way for the rest of the game. A common objective with respect to some infinite graph G is to determine how many firefighters are necessary to stop the fire from spreading after a finite number of turns, commonly referred to as containing the fire. We introduce the concept of distance-restricted firefighting where the firefighters’ movement is restricted so they can only move up to some fixed distance d per turn rather than being able to move without restriction. We establish some general properties of this new game in contrast to properties of the original game, and we investigate specific cases of the distance-restricted game on the infinite strong, hexagonal, and square grids. We conjecture that two firefighters are insufficient on the square grid when d =2, and we pose some questions about how many firefighters are required in general when d = 1.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/15648
Item ID: 15648
Additional Information: Includes bibliographical references (pages 35-36)
Keywords: combinatorics, graph theory, graph searching, pursuit evasion
Department(s): Science, Faculty of > Mathematics and Statistics
Date: August 2022
Date Type: Submission
Digital Object Identifier (DOI): https://doi.org/10.48336/ZSGZ-EC19
Library of Congress Subject Heading: Graph theory; Combinatorial analysis; Fire Fighter (Game)

Actions (login required)

View Item View Item


Downloads per month over the past year

View more statistics