E-viri
Recenzirano
Odprti dostop
-
Duchêne, Eric; Dumas, Arthur; Oijid, Nacim; Parreau, Aline; Rémila, Eric
Discrete Applied Mathematics, 05/2024, Letnik: 348Journal Article
We study the Maker–Maker version of the domination game introduced in 2018 by Duchêne et al. Given a graph, two players alternately claim vertices. The first player to claim a dominating set of the graph wins. As the Maker–Breaker version, this game is PSPACE-complete on split and bipartite graphs. Our main result is a linear time algorithm to solve this game in forests. We also give a characterization of the cycles where the first player has a winning strategy.
