Controlando o fogo nos fulerenos

• Sérgio Fusquino UERJ
• Diego Nicodemos UERJ / Colégio Pedro II
• Diana Sasaki UERJ

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

Abstract

The Firefighter problem was introduced by Hartnell in 1995 and corresponds to a scenario in which a fire breaks out at one or more vertices of a graph and spreads to all adjacent vertices that have not been protected in previous steps. In this paper, we present an algorithm of the Firefighter problem to an infinite family of fullerene graphs with full icosahedral symmetry, providing a surviving rate of at least 50%.

References

Cai, L. e Wang, W. (2009). The Surviving Rate of a Graph for the Firefighter Problem. Discrete Math, 23:1814–1826.

Costa, V. (2015). Estudando Emparelhamentos e Combatendo Incêndios: Em Busca de Novos Limites em Teoria dos Grafos. PhD thesis, Universidade Federal Fluminense.

Finbow, S., King, A., MacGillivray, G., e Rizzi, R. (2007). The firefighter problem for graphs of maximum degree three. Discrete Math, 307:2094–2105.

Fusquino, S., Sasaki, D., e Nicodemos, D. (2023). The dodecahedron is on fire. Submitted.

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

Kroto, H. W., Heath, J. R., O’Brien, S. C., Curl, R. F., e Smalley, R. E. (1985). c₆₀: Buckminsterfullerene. Nature, 318:162–163.