Abstract: We introduce the Maker-Breaker domination game, a two player game on a graph. At his turn, the first player, Dominator, select 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.
Recommendations
Cites work
- A Linear Recognition Algorithm for Cographs
- A Solution of the Shannon Switching Game
- Biased Positional Games
- Combinatorial Games
- Combinatorial game theory
- Domination game and an imagination strategy
- Domination game on paths and cycles
- Domination game played on trees and spanning subgraphs
- Extremal problems for game domination number
- Game domination number
- On a combinatorial game
- On the complexity of some two-person perfect-information games
- Packings by cliques and by finite families of graphs
- Positional games
- Proof of a conjecture on game domination
- The disjoint domination game
- The domination game played on unions of graphs
Cited in
(19)- Fast winning strategies for staller in the maker-breaker domination game
- Maker-breaker resolving game
- Complexity of maker-breaker games on edge sets of graphs
- Waiter-client triangle-factor game on the edges of the complete graph
- Maker-breaker total domination game
- Maker-breaker domination number
- The maker-breaker largest connected subgraph game
- Maker-Breaker total domination game on cubic graphs
- Connected domination game played on Cartesian products
- Maker-breaker domination game on trees when Staller wins
- Maker-breaker domination number for Cartesian products of path graphs \(P_2\) and \(P_n\)
- Predominating a vertex in the connected domination game
- \( 1 / 2\)-conjectures on the domination game and claw-free graphs
- 6-uniform Maker-Breaker game is PSPACE-complete
- Indicated domination game
- Thresholds for the monochromatic clique transversal game
- The maker-maker domination game in forests
- A proof of the 3/4-conjecture for the total domination game
- Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
This page was built for publication: Maker-Breaker domination game
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776271)
