DIMACS TR: 2006-11

Blocking sequences of sets in infinite graphs

Authors: James Abello and Michael Capalbo


In this paper, we introduce the graph-theoretic concept of a blocking sequence, and use that concept to prove a conjecture about certain instances of the Firefighter Problem.

More specifically, for any positive integer $d$, let $H^d$ be a $d$-dimensional infinite grid, where at each time-step ($0,1,2, \ldots$), each vertex is in one of three states: {\em on-fire}, {\em fireproofed}, or {\em suseptible}, where a vertex that is suseptible becomes on-fire for the next time step if any of its neighbors are on-fire already, unless it is fireproofed first. Suppose that at time-step 0, some finite set $S_0$ of vertices is on-fire, and that at each time-step $t$, we are allowed to fireproof $f(t)$ vertices of $H^d$ to contain the set of vertices that eventually become on-fire to a finite set. Hartke conjectured in his Ph.D. thesis that $f(t)$ would have to be $\Omega(t^{d-2})$ for us to be successful for all such $S_0$. The main result of this paper is that we prove his conjecture to be correct.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-11.ps.gz

DIMACS Home Page