Maker-Breaker domination game

DOI10.1016/J.DISC.2020.111955zbMATH Open1443.05126arXiv1807.09479OpenAlexW3028095874MaRDI QIDQ776271FDOQ776271

Valentin Gledel, E. Duchêne, Gabriel Renault, Aline Parreau

Publication date: 8 July 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1807.09479

Recommendations

• Maker-breaker total domination game
• Maker-breaker domination number
• The disjoint domination game
• Maker-Breaker total domination game on cubic graphs
• Domination game on paths and cycles

zbMATH Keywords

treecomplexitypositional gamesdomination gamecographMaker-Breaker domination game

Mathematics Subject Classification ID

Trees (05C05) 2-person games (91A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Combinatorial game theory
• Domination Game and an Imagination Strategy
• The domination game played on unions of graphs
• Extremal Problems for Game Domination Number
• Positional games
• Biased Positional Games
• Combinatorial Games
• A Solution of the Shannon Switching Game
• On a combinatorial game
• Domination game played on trees and spanning subgraphs
• The disjoint domination game
• A Linear Recognition Algorithm for Cographs
• On the complexity of some two-person perfect-information games
• Packings by cliques and by finite families of graphs
• Game domination number
• Proof of a conjecture on game domination
• Domination game on paths and cycles

Cited In (19)

• Maker-Breaker total domination game on cubic graphs
• 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
• Fast winning strategies for staller in the maker-breaker domination game
• Waiter-client triangle-factor game on the edges of the complete graph
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Maker-breaker resolving game
• Maker-breaker total domination game
• 6-uniform Maker-Breaker game is PSPACE-complete
• Maker-breaker domination number
• Connected domination game played on Cartesian products
• The maker-breaker largest connected subgraph game
• \( 1 / 2\)-conjectures on the domination game and claw-free graphs
• Complexity of maker-breaker games on edge sets of graphs
• Thresholds for the monochromatic clique transversal game
• A proof of the 3/4-conjecture for the total domination game
• The maker-maker domination game in forests
• Indicated domination game

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)