Title of article :
Biased orientation games
Author/Authors :
Ben-Eliezer، نويسنده , , Ido and Krivelevich، نويسنده , , Michael and Sudakov، نويسنده , , Benny، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
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
Journal title :
Discrete Mathematics