On two problems regarding the Hamiltonian cycle game (Q1010935)

Summary: We consider the fair Hamiltonian cycle maker-breaker game, played on the edge set of the complete graph \(K_n\) on \(n\) vertices. It is known that maker wins this game if \(n\) is sufficiently large. We are interested in the minimum number of moves needed for Maker in order to win the Hamiltonian cycle game, and in the smallest \(n\) for which maker has a winning strategy for this game. We prove the following results: (1) If \(n\) is sufficiently large, then maker can win the Hamiltonian cycle game within \(n+1\) moves. This bound is best possible and it settles a question of \textit{D. Hefetz, Dan; M. Krivelevich, M. Stojaković} and \textit{T. Szabó} [J. Comb. Theory, Ser. B 99, No. 1, 39--47 (2009; Zbl 1214.05062)]; (2) If \(n \geq 29\), then maker can win the Hamiltonian cycle game. This improves the previously best bound of \(600\) due to \textit{A. Papaioannou} [Ann. Discrete Math. 13, 171--178 (1982; Zbl 0492.05052)].