2025/07/23 by Brešar, Boštjan, Dravec, Tanja, Kuenzel, Kirsti +1
#05C57 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.17646
The Maker-Breaker domination game is played on a graph G by Dominator and Staller who alternate turns selecting an unplayed vertex of G. The goal of Dominator is that the vertices he selected during the game form a dominating set while Staller's goal is to prevent this from happening. The graph invariant γ\rm MB'(G) is the number of Dominator's moves in the game played on G in which he can achieve his goal when Staller makes the first move and both players play optimally. In this paper, we continue the investigation of 2-γ\rm MB'-critical graphs, initiated in [Divarakan et al., Maker--Breaker domination game critical graphs, Discrete Appl. Math. 368 (2025) 126--134], which are defined as the graphs G with γ\rm MB'(G)=2 and γ\rm MB'(G-e)>2 for every edge e in G. The authors characterized bipartite 2-γ\rm MB'-critical graphs, and found an example of a non-bipartite 2-γ\rm MB'-critical graph. In this paper, we characterize the 2-γ\rm MB'-critical graphs that have a cut-vertex, which are represented by two infinite families. In addition, we prove that C5 is the only non-bipartite, triangle-free 2-γ\rm MB'-critical graph.