2022/06/26 by Csilla Bujtás, Bujtás, Csilla, Pakanun Dokyeesun +1 · 1 citation
Computer Science · Decision Sciences · #05C57 #05C65 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2206.12812
openalex publication_date 2022/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Maker-Breaker domination game is played on a graph G by two players, called Dominator and Staller, who alternately choose a vertex that has not been played so far. Dominator wins the game if his moves form a dominating set. Staller wins if she plays all vertices from a closed neighborhood of a vertex v ∈ V(G). Dominator's fast winning strategies were studied earlier. In this work, we concentrate on the cases when Staller has a winning strategy in the game. We introduce the invariant γ'\rm SMB(G) (resp., γ\rm SMB(G)) which is the smallest integer k such that, under any strategy of Dominator, Staller can win the game by playing at most k vertices, if Staller (resp., Dominator) plays first on the graph G. We prove some basic properties of γ\rm SMB(G) and γ'\rm SMB(G) and study the parameters' changes under some operators as taking the disjoint union of graphs or deleting a cut vertex. We show that the inequality δ(G)+1 ≤ γ'\rm SMB(G) ≤ γ\rm SMB(G) always holds and that for every three integers r,s,t with 2≤ r≤ s≤ t, there exists a graph G such that δ(G)+1 = r, γ'\rm SMB(G) = s, and γ\rm SMB(G) = t. We prove exact formulas for γ'\rm SMB(G) where G is a path, or it is a tadpole graph which is obtained from the disjoint union of a cycle and a path by adding one edge between them.