Jogo Normal Partizan de Dominação nas Estrelas

• João Marcos Brito UFC
• Edileudo Maciel M. Filho UFC
• Jefter G. Maciel Paz UFC
• Rudini Sampaio UFC

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

Resumo

O Jogo de Dominação em grafos foi criado em 2010 e sua variante normal só foi provada PSPACE-completa em 2026. Nesse artigo, determinamos o vencedor do Jogo Normal Partizan de Dominação na união de grafos split completos para qualquer coloração dos vértices, incluindo florestas de estrelas.

Referências

Araújo, S., Martins, N., Nisse, N., and Sampaio, R. (2026). Theory of Combinatorial Games in Graphs. Springer Undergraduate Texts in Mathematics and Technology (SUMAT), Springer Cham.

Berlekamp, E. R., Conway, J. H., and Guy, R. K. (1982). Winning Ways for Your Mathematical Plays, volume 1. Academic Press.

Brešar, B., Klavžar, S., and Rall, D. F. (2010). Domination game and an imagination strategy. SIAM J. Discrete Math., 24(3):979–991.

Brešar, B., Dorbec, P., Klavžar, S., Košmrlj, G., and Renault, G. (2016). Complexity of the game domination problem. Theoretical Computer Science, 648:1–7.

Brito, J. M., Marcilon, T., Martins, N. A., and Sampaio, R. M. (2026). The normal domination game in graphs. J. Comput. Syst. Sci., 157:103751.

Conway, J. H. (1976). On numbers and games. L.M.S. monographs ; no. 6. Academic Press, London.

Siegel, A. N. (2013). Combinatorial Game Theory. Graduate studies in mathematics. American Math. Soc.