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.
Original language | English |
---|---|
Pages (from-to) | 169-183 |
Journal | European Journal of Combinatorics |
Volume | 35 |
Early online date | 4 Jul 2013 |
DOIs | |
Publication status | Published - 1 Jan 2014 |