On two problems regarding the Hamiltonian cycle game
The electronic journal of combinatorics, Tome 16 (2009) no. 1
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 Hefetz, Krivelevich, Stojaković and Szabó; (2) If $n \geq 29$, then Maker can win the Hamiltonian cycle game. This improves the previously best bound of $600$ due to Papaioannou.
@article{10_37236_117,
author = {Dan Hefetz and Sebastian Stich},
title = {On two problems regarding the {Hamiltonian} cycle game},
journal = {The electronic journal of combinatorics},
year = {2009},
volume = {16},
number = {1},
doi = {10.37236/117},
zbl = {1161.91011},
url = {http://geodesic.mathdoc.fr/articles/10.37236/117/}
}
Dan Hefetz; Sebastian Stich. On two problems regarding the Hamiltonian cycle game. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/117
Cité par Sources :