The additive 1/2-conjecture for the domination game

Let GG be a graph on nn vertices with 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. Bujtás–Iršič–Klavžar's additive conjecture. There exists a universal constant CC such that

γg(G)12n+C.\gamma_g(G) \leq \frac{1}{2}n+C.

This is a relaxation of the conjectured bound γg(G)n/2\gamma_g(G) \leq \lceil n/2\rceil for graphs of minimum degree at least 22. The paper's 10n/17+1/1710n/17+1/17 result does not reach the coefficient 1/21/2, so this 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.