Domination game: state of the art

2016-05-30
10:00-11:00
FAMNIT-POŠTA
Boštjan Brešar (University of Maribor)
Domination game: state of the art

The domination game is played on a graph $G$ by two players, Dominator and Staller. They are alternating turns in choosing vertices, one at a time, so that each chosen vertex enlarges the set of vertices of $G$ dominated to that point in the game. The game ends when all vertices of $G$ are dominated. The aim of Dominator is that the game ends in as few moves as possible, while Staller’s goal is to maximize the number of moves. Assuming that both players play optimally, and that Dominator starts the game, the number of vertices chosen in the game is called the game domination number, $gamma_g(G)$; if Staller starts the game, we denote the resulting number of moves by $gamma_g'(G)$.

The domination game was introduced in 2010, and received a considerable attention by several authors. In this talk, I intend to give a brief overview of the results and methods related to the domination game. In particular, $3/5$-conjectures, relations between both versions of the game, and complexity issues will be presented.