The Maker–Maker domination game in forests

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....

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2024-05, Vol.348, p.6-34
Main Authors: Duchêne, Eric, Dumas, Arthur, Oijid, Nacim, Parreau, Aline, Rémila, Eric
Format: Article
Language:English
Subjects:
Combinatorics
Computational Complexity
Computer Science
Dominating set
Domination game
Graphs
Maker–Breaker games
Maker–Maker games
Mathematics
Positional games
PSPACE-completeness
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2024.01.023