2012/03/15 by Asaf Ferber, Ferber, Asaf, Dan Hefetz +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Search Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1203.3447
arxiv created 2012/03/15 · openalex publication_date 2012/03/15 · arxiv updated 2012/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 for winning this game within \lfloor k n/2 \rfloor + 1 moves, which is clearly best possible. This answers a question of Hefetz, Krivelevich, Stojaković and Szabó. 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.