# Valentin Gledel: Maker-Breaker Domination Game

Date: 25. 2. 2018

Source: Discrete mathematics seminar

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.