Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424188 | European Journal of Combinatorics | 2014 | 15 Pages |
Abstract
For a positive integer k, we consider the k-vertex-connectivity game, played on the edge set of Kn, the complete graph on n vertices. We first study the Maker-Breaker version of this game and prove that, for any integer kâ¥2 and sufficiently large n, Maker has a strategy to win this game within âkn/2â+1 moves, which is easily seen to be best possible. This answers a question from Hefetz et al. (2009) [6]. We then consider the strong k-vertex-connectivity game. For every positive integer k and sufficiently large n, we describe an explicit first player's winning strategy for this game.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Asaf Ferber, Dan Hefetz,