Maker-Breaker domination game

12th of May 2022, at 15:00

Room: Online via Teams

Cliquez ici pour participer à la réunion

Speaker: Valentin Gledel

Title: Maker-Breaker domination game

Abstract:

The Maker-Breaker domination game is a two player game played on a graph. The two players, Dominator and Staller, alternatively select vertices of the graph. If at some point, the vertices selected by Dominator form a dominating set, he wins the game. If however Staller can keep Dominator from ever dominating the graph, she wins the game. 

As in every two player game with perfect information, one of the two players is bound to have a winning strategy. The goal of this talk will be to study two problems: the first one is to determine which player has a winning strategy and the other one is to know the number of moves Dominator needs to play to win the game, assuming he has a winning strategy. We give complexity results for both of these problems.