Bujtás–Iršič–Klavžar's strict 3/5 improvement conjecture for the domination game

Let GG be a graph on n6n \geq 6 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 conjecture. There exists a constant c<3/5c < 3/5 such that

γg(G)cn.\gamma_g(G) \leq cn.

This conjecture seeks a uniform improvement over the general 3n/53n/5 upper bound for graphs without isolated vertices, specifically for graphs without leaves. The paper's main theorem gives the bound 10n/17+1/1710n/17+1/17, but does not establish the existence of a constant below 3/53/5.

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.