Rall's 1/2-conjecture on the domination game

Let GG be a graph, and let n(G)n(G) denote its order. The graph GG is traceable if it contains a Hamiltonian path, and γg(G)\gamma_g(G) denotes its game domination number in the Dominator-start game.

Rall's 1/2-conjecture. If GG is traceable, then

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

The conjecture was proposed by D. Rall and first published by James et al. The paper proves it for unicyclic graphs and establishes it for several additional graph families, but the general case remains open.

Sources & referencesView supporting material

Primary source

Csilla Bujtás, Vesna Iršič, Sandi Klavžar and Kexiang Xu, “On Rall's 1/2-conjecture on the domination game”, arXiv:2006.02668 (2020).

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.