
arXiv: 1902.00204
Maker-Breaker total domination game in graphs is introduced as a natural counterpart to the Maker-Breaker domination game recently studied by Duch��ne, Gledel, Parreau, and Renault. Both games are instances of the combinatorial Maker-Breaker games. The Maker-Breaker total domination game is played on a graph $G$ by two players who alternately take turns choosing vertices of $G$. The first player, Dominator, selects a vertex in order to totally dominate $G$ while the other player, Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. It is shown that there are infinitely many connected cubic graphs in which Staller wins and that no minimum degree condition is sufficient to guarantee that Dominator wins when Staller starts the game. An amalgamation lemma is established and used to determine the outcome of the game played on grids. Cacti are also classified with respect to the outcome of the game. A connection between the game and hypergraphs is established. It is proved that the game is PSPACE-complete on split and bipartite graphs. Several problems and questions are also posed.
21 pages, 5 figures
Cartesian product of graphs, Games on graphs (graph-theoretic aspects), Graph operations (line graphs, products, etc.), 05C57, 05C69, 68Q25, 91A43, hypergraph, maker-breaker domination game, Hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), maker-breaker total domination game, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, cactus, Combinatorics (math.CO), PSPACE-completeness
Cartesian product of graphs, Games on graphs (graph-theoretic aspects), Graph operations (line graphs, products, etc.), 05C57, 05C69, 68Q25, 91A43, hypergraph, maker-breaker domination game, Hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), maker-breaker total domination game, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, cactus, Combinatorics (math.CO), PSPACE-completeness
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
