Title of article :
Biased orientation games
Author/Authors :
Ben-Eliezer، نويسنده , , Ido and Krivelevich، نويسنده , , Michael and Sudakov، نويسنده , , Benny، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Pages :
11
From page :
1732
To page :
1742
Abstract :
We study biased orientation games, in which the board is the complete graph K n , and OMaker (oriented maker) and OBreaker (oriented breaker) take turns in directing previously undirected edges of K n . At the end of the game, the obtained graph is a tournament. OMaker wins if the tournament has some property P and OBreaker wins otherwise. vide bounds on the bias that is required for OMaker’s win and for OBreaker’s win in three different games. In the first game OMaker wins if the obtained tournament has a cycle. The second game is Hamiltonicity, where OMaker wins if the obtained tournament contains a Hamilton cycle. Finally, we consider the H -creation game, where OMaker wins if the obtained tournament has a copy of some fixed digraph H .
Keywords :
directed graphs , Orientation games , Hamiltonicity
Journal title :
Discrete Mathematics
Serial Year :
2012
Journal title :
Discrete Mathematics
Record number :
1599973
Link To Document :
بازگشت