Weak and strong -connectivity games

For a positive integer k , we consider the k -vertex-connectivity game, played on the edge set of K n , 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 ⌊ k n / 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.