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

Resumo

O problema do Bombeiro foi introduzido por Hartnell em 1995 e consiste em um incêndio que começa em um ou mais vértices de um grafo e se espalha para todos os vértices adjacentes que ainda não foram protegidos. Neste trabalho nós apresentamos um algoritmo do problema do Bombeiro para uma família infinita de grafos fulerenos com simetria icosaedral completa, fornecendo uma taxa de sobrevivência de pelo menos 50%.

Referências

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.