2025/03/14 by Brešar, Boštjan, Bujtás, Csilla, Dokyeesun, Pakanun +1 · 1 citation
#05C57 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.11871
In the (a,b)-biased Maker-Breaker domination game, two players alternately select unplayed vertices in a graph G such that Dominator selects a and Staller selects b vertices per move. Dominator wins if the vertices he selected during the game form a dominating set of G, while Staller wins if she can prevent Dominator from achieving this goal. Given a positive integer b, Dominator's threshold, \textrmab, is the minimum a such that Dominator wins the (a,b)-biased game on G when he starts the game. Similarly, \textrma'b denotes the minimum a such that Dominator wins when Staller starts the (a,b)-biased game. Staller's thresholds, \textrmba and \textrmb'a, are defined analogously. It is proved that Staller wins the (k-1,k)-biased games in a graph G if its order is sufficiently large with respect to a function of k and the maximum degree of G. Along the way, the ℓ-local domination number of a graph is introduced. This new parameter is proved to bound Dominator's thresholds \textrma_ℓ and \textrma_ℓ' from above. As a consequence, \textrma1'(G)≤ 2 holds for every claw-free graph G. More specific results are obtained for thresholds in line graphs and Cartesian grids. Based on the concept of [1,k]-factor of a graph G, we introduce the star partition width σ(G) of G, and prove that \textrma1'(G)≤ σ(G) holds for any nontrivial graph G, while \textrma1'(G)=σ(G) if G is a tree.