Rall's Hamiltonian-path conjecture for the domination game

About 3 years old · traced to

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.

References

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.