The one-half Minimizer-start Enclaveless Game Conjecture

At least 5 years old · documented by

Let GG be a graph of order nn, and let δ(G)\delta(G) denote its minimum degree. In the Minimizer-start competition-enclaveless game, Minimizer starts, and Ψg−(G)\Psi_g^-(G) is the number of vertices chosen when both players use optimal strategies. The one-half Minimizer-start Enclaveless Game Conjecture.

δ(G)≥2⟹Ψg−(G)≥12n.\delta(G) \ge 2 \quad\Longrightarrow\quad \Psi_g^-(G) \ge \frac{1}{2}n.

This conjecture gives a corresponding lower bound for the Minimizer-start version of the competition-enclaveless game. The source presents it as one of the main unsettled questions motivating the paper.

References

Primary source

Michael A. Henning and Douglas F. Rall, “The Enclaveless Competition Game”, arXiv:2006.02829 (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.