Firefighters work better when the bandwidth is small

• Sérgio Fusquino UERJ
• Luerbio Faria UERJ
• Diana Sasaki UERJ
• Vinicius dos Santos UFMG

DOI: https://doi.org/10.5753/etc.2024.2508

Resumo

In this work we address the Firefighter problem in graphs and its relationship with the bandwidth parameter bw(G) of a graph G. The Firefighter problem consists of a scenario in which a vertex v of the graph is initially set on fire, which we call the focus of the fire. The objective is to defend the largest number of vertices not on fire with firefighters, protecting vertex by vertex, as the fire spreads after each new defense. The bandwidth parameter in graphs is a minimum natural number, such that it is found after an optimal linear arrangement of the vertices, such that the distance between the indices of the vertices of this linear arrangement is the smallest possible. We relate this parameter to Firefighter to find a lower bound on the maximum number of vertices saved from fire in a graph G.

Referências

Chung, F. (1988). Selected topics in graph theory. Academic Press.

Chvátal, V. (1970). A remark on a problem of harary. Czechoslovak Mathematical Journal, 20:109–111.

Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman.

Hartnell, B. (1995). Firefighter! An application of domination. In The 25th Manitoba Conference on Combinatorial Mathematics and Computing.