Speed and size of dominating sets in domination games


Yannick Mogge, Hamburg University of Technology. 14 novembre 2024 10:00 TLR limd
Abstract:

We consider Maker-Breaker domination games, a variety of positional games, in which two players (Dominator and Staller) alternately claim vertices of a given graph. Dominator's goal is to fully claim all vertices of a dominating set, while Staller tries to prevent Dominator from doing so, or at least tries to delay Dominator's win for as long as possible.

We prove a variety of results about domination games, including the number of turns Dominator needs to win and the size of a smallest dominating set that Dominator can occupy. We could also show that speed and size can be far apart, and we prove further non-intuitive statements about the general behaviour of such games.

We also consider the Waiter-Client version of such games.

Co-authors (all from Hamburg University of Technology as well): Ali Deniz Bagdas, Dennis Clemens, Fabian Hamann