ANALYSIS OF SAVING SETS AND SURVIVING RATES IN THE FIREFIGHTER PROBLEM WITH EDGES SUBDIVISION ON GRAPHS OF MAXIMUM DEGREE 3 AND FULL k-ARY TREE

Abstract

Abstract. This study investigates a firefighter problem model that includes the strategy of edge subdivision. In this model, the firefighter can add a new vertex along an edge that is incident to a burning vertex; the new vertex immediately catches fire, effectively creating a tactical fire break that slows the fire’s spread. Our first main goal is to understand the structure of the Sub-SFire problem. We identify the exact structural rules (necessary and sufficient conditions) that guarantee the existence of a strategy to save a specific set of vertices S in rooted graphs with maximum degree 3. Next, we extend the analysis to allow m subdivisions per round on full k-ary tree. We derive exact formulas for the number of burned vertices |B<inf>T</inf>| and the surviving rate ρsub(G). Numerical results for k=4 show that the rate of saved vertices quickly reaches a stable maximum close to 1.0 as the tree grows deeper.