The 1/2-conjecture for the domination game

Let GG be a graph with nn vertices and minimum degree at least 22. The game domination number γg(G)\gamma_g(G) is the number of moves in the domination game when Dominator starts and both players play optimally. The 1/2-conjecture.

γg(G)12n.\gamma_g(G) \leq \left\lceil \frac{1}{2}n \right\rceil.

This is the stronger target for graphs without leaves, improving the known general 3n/53n/5 bound. The paper proves 10n/17+1/1710n/17+1/17, which is progress toward the conjecture, but the conjecture remains open.

Sources & referencesView supporting material

Primary source

Julien Portier and Leo Versteegen, “Progress towards the 1/2-Conjecture for the domination game”, arXiv:2301.05202 (2023).

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.