Weak and strong k-connectivity games

Abstract: 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 g e q 2

and sufficiently large

n

, Maker has a strategy for winning this game within

l f l o o r k n / 2 f l o o r + 1

moves, which is clearly best possible. This answers a question of Hefetz, Krivelevich, Stojakovi'c and Szab'o. 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.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Weak and strong \(k\)-connectivity games