NUK - logo
E-viri
Recenzirano Odprti dostop
  • Maker–Breaker domination game
    Duchêne, Eric; Gledel, Valentin; Parreau, Aline; Renault, Gabriel

    Discrete mathematics, September 2020, 2020-09-00, 2020-09, Letnik: 343, Številka: 9
    Journal Article

    We introduce the Maker–Breaker domination game, a two player game on a graph. At his turn, the first player, Dominator, selects a vertex in order to dominate the graph while the other player, Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. Both players play alternately without missing their turn. This game is a particular instance of the so-called Maker–Breaker games, that is studied here in a combinatorial context. In this paper, we first prove that deciding the winner of the Maker–Breaker domination game is pspace-complete, even for bipartite graphs and split graphs. It is then showed that the problem is polynomial for cographs and trees. In particular, we define a strategy for Dominator that is derived from a variation of the dominating set problem, called the pairing dominating set problem.