Weak and Strong k-connectivity games

Details Weak and Strong k-connectivity games Weak and Strong k-connectivity games

2012-03-15

arxiv.org/abs/1203.3447v1

Mathematics

Combinatorics

Scientific paper

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 \geq 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\'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.

Affiliated with

Also associated with

No associations

Rating

Weak and Strong k-connectivity games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Weak and Strong k-connectivity games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weak and Strong k-connectivity games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-31976