Jogo normal de dominação em grafos: estratégias vencedoras e complexidade computacional

Abstract

Impartial Combinatorial Game Theory is a branch of mathematics that studies mathematical models of conflict and cooperation among individuals by modeling them as games that must satisfy certain criteria: two players alternating turns, a finite set of moves, perfect information, no randomness, and both players having the same set of possible moves in any position of the game. Around 1930, independently, Sprague and Grundy developed a theory stating that we can assign a non-negative integer value (nimber) to any position of an impartial combinatorial game and, with this, determine which of the two players will be the winner from the analyzed position. In parallel, we say that a set of vertices D dominates a graph G if every vertex of G is either in D or is adjacent to some vertex in D. With this, we can consider the DOMINATION GAME on graphs, an impartial combinatorial game in which two players alternately choose a vertex that has not yet been chosen and that must dominate at least one vertex that has not yet been dominated. The game ends when there are no more playable vertices, that is, when the chosen set of vertices forms a dominating set of the graph. This game has three versions: normal (the last player to move wins), misère (the last player to move loses), and optimization. In the optimization version, a player wins if they manage to finish the game in a number of turns less than or equal to a positive value k, and the opponent wins otherwise. In the literature there are many results for the optimization version of this game, but nothing has been found about the normal and misère versions. Therefore, in this work we present results for these versions. We use the Sprague-Grundy Theory to solve the NORMAL DOMINATION GAME on paths and cycles. In addition, we present a proof of the PSPACE-completeness of the DOMINATION GAME in its normal and misère versions.