Valentin Gledel: Maker-Breaker Domination Game
Vir: Seminar za diskretno matematiko
Povzetek. The Maker-Breaker Domination Game is played on a graph G. Two players, Dominator and Staller, alternatively select a vertex previously unselected. Dominator wins if the vertices he selected form a dominating set and Staller wins if Dominator is unable to form such a set, i.e. if there exists a vertex such that its closed neighborhood is selected by Staller. This game can also be seen as instances of the POS-CNF game introduced by Schaefer.
We prove that this game is PSPACE-complete on split graphs and bipartite graphs, and that it is polynomial on trees and cographs.