On two problems regarding the Hamiltonian cycle game
type: Item
instance of: scholarly article
title: On two problems regarding the Hamiltonian cycle game
zbMATH Open document ID: 1161.91011
author: Dan Hefetz
author: S. U. Stich
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129913
full work available at URL: v16i1r28.html
review text: 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)].
Mathematics Subject Classification ID: 91A46
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 5541093
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5541093