100
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

Hamiltonian Maker–Breaker Games on Small Graphs

ORCID Icon & ORCID Icon
 

Abstract

We look at the unbiased Maker–Breaker Hamiltonicity game played on the edge set of a complete graph Kn, where Maker’s goal is to claim a Hamiltonian cycle. First, we prove that, independent of who starts, Maker can win the game for n = 8 and n = 9. Then we use an inductive argument to show that, independent of who starts, Maker can win the game if and only if n8. This, in particular, resolves in the affirmative the long-standing conjecture of Papaioannou. We also study two standard positional games related to Hamiltonicity game. For Hamiltonian Path game, we show that Maker can claim a Hamiltonian path if and only if n5, independent of who starts. Next, we look at Fixed Hamiltonian Path game, where the goal of Maker is to claim a Hamiltonian path between two predetermined vertices. We prove that if Maker starts the game, he wins if and only if n7, and if Breaker starts, Maker wins if and only if n8. Using this result, we are able to improve the previously best upper bound on the smallest number of edges a graph on n vertices can have, knowing that Maker can win the Maker–Breaker Hamiltonicity game played on its edges. To resolve the outcomes of the mentioned games on small (finite) boards, we devise algorithms for efficiently searching game trees and then obtain our results with the help of a computer.

Notes

1 If P is Maker, he won if he claimed a whole winning set, and if P is Breaker, he won if he claimed an edge in each of the winning sets.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.