The Firefighter Problem Of Graphs

Let G be a connected graph with n≥2 vertices. We denote its vertex set by V(G). This thesis is motivated by the firefighter problem on a graph put forward by Hartnell at a conference in 1995. Let G be a connected graph and v a vertex of G, i.e. v∈V(G). In the simplest form of the problem, we suppose that a fire breaks out at v. A firefighter chooses a vertex not yet on fire to protect. Then the firefighter and the fire alternately move on the graph. Once a vertex has been chosen by the firefighter, it is considered protected or safe from any further moves of the fire. After the firefighter moves, the fire makes its move by spreading to all unprotected vertices which are adjacent to a vertex on fire. The process ends when the fire can no longer spread.We use sn(v) to denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v, which can be referred to as the surviving number for v. The surviving rate p(G) of G is defined to be the average proportion of vertices that can be saved when a fire breaks out at one vertex of the graph, that is, p(G)=sn(V(G))/n2.This thesis aims at the k-surviving rate, investigating some planar graphs on fire-fighter problems.In Chapter 2, the main result is that if H is a Halin graph with n vertices, n→∞limρ2(H)= 1 exists.In Chapter 3, we investigate the surviving rate of outerplanar graphs G with n≥2 vertices. Two results are obtained as follows:(1) n→∞limρ5(G)= 1;(2)ρ1(G)≥43/81-5/3n+3/n2 if n≥8; andρ1(G)≥1/3 if n≥2.In Chapter 4, we investigate the surviving rate of square grids and triangular grids. For square grids Pn×n, we obtain:(1)ρ1(Pn×n) is at least 5/8 when n is sufficiently large; (2)(?)ρ2(Pn×n)=1.For triangular grids Tn×n,we get:(3)ρ1(Tn×n)is at least 41/96 when n is sufficiently large;(4)(?)ρ3(Tn×n)=1.