Rall's Hamiltonian-path conjecture for the domination game

Let GG be a graph on nn vertices. A Hamiltonian path is a path containing every vertex of GG exactly once. 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. Rall's conjecture. If GG has a Hamiltonian path, then

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

The paper proves the weaker bound 10n/17\lceil 10n/17\rceil for graphs with a Hamiltonian path. Thus the conjectured half-order bound 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.