Home > News > Valentin Gledel: Maker-Breaker Domination Game

Valentin Gledel: Maker-Breaker Domination Game

Date: 25. 2. 2018
Source: Discrete mathematics seminar
Torek, 27. 2. 2018, od 10h do 12h, Plemljev seminar, Jadranska 19

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.