Equality of Maker–Breaker domination parameters for random graphs

Let GG be a random graph, and let γMB(G,b)\gamma_{MB}(G,b) and sMB(G,b)s_{MB}(G,b) denote the two Maker–Breaker domination game parameters. For a Binomial random graph Gn,pG_{n,p} with constant edge probability p(0,1)p\in (0,1), or a random geometric graph G2(n,r)\mathcal{G}_2(n,r) with constant radius r(0,1)r\in (0,1), the random-graph equality conjecture.

γMB(G,b)=sMB(G,b)\gamma_{MB}(G,b)=s_{MB}(G,b)

holds with high probability.

The conjecture predicts that these two game parameters coincide asymptotically almost surely in the stated random-graph models. The surrounding discussion notes that related Maker–Breaker domination parameters asymptotically equal the domination number with high probability; the equality with sMBs_{MB} remains conjectural.

Sources & referencesView supporting material

Primary source

Ali Deniz Bagdas, Dennis Clemens, Fabian Hamann and Yannick Mogge, “Constructions for positional games and applications to domination games”, arXiv:2509.05089 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.