The Firefighter Game in Fullerene Graphs

Resumo

In 1995, Hartnell introduced the Firefighter game with an input graph G = (V,E). Initially, every vertex of V is labelled non-burned. The game consists of a fire starting at vertex v ∈ V switching the label of v to burned. While there are non-burned vertices adjacent to burned vertices (the fire is still spreading), a non-burned vertex u is chosen to be defended, setting the label of u to defended. At each new step, the fire spreads from each burned vertex v to every non-burned adjacent vertices to v, which labels are set to burned. The game ends when the fire is no longer able to spread. We want to defend as many vertices as possible. Let sn(G, v) be the maximum number of vertices that can be defended when a fire starts from a vertex v ∈ V. The surviving rate ρ(G) = 1/|V|^2 ∑v∈V sn(G, v) is the average percentage of vertices that can be defended when a fire starts from a vertex v of V. In this work, we apply a Firefighter game to fullerene graphs. We established ρ(G), when G is the full icosahedral symmetry fullerene graph G2,0.