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
1
Issued Date
2026-04-01
Resource Type
ISSN
1881803X
Scopus ID
2-s2.0-105032226522
Journal Title
Icic Express Letters
Volume
20
Issue
4
Start Page
373
End Page
380
Rights Holder(s)
SCOPUS
Bibliographic Citation
Icic Express Letters Vol.20 No.4 (2026) , 373-380
Suggested Citation
Weeranukunjit C., Lewchalermvong C. 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. Icic Express Letters Vol.20 No.4 (2026) , 373-380. 380. doi:10.24507/icicel.20.04.373 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/115695
Title
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
Author(s)
Author's Affiliation
Corresponding Author(s)
Other Contributor(s)
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.