科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 left perpendiculark(n)/2right perpendicular + 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.
- 出版日期2014-1
