Article ID Journal Published Year Pages File Type
4648101 Discrete Mathematics 2012 11 Pages PDF
Abstract

We study biased orientation games  , in which the board is the complete graph KnKn, and OMaker (oriented maker) and OBreaker (oriented breaker) take turns in directing previously undirected edges of KnKn. At the end of the game, the obtained graph is a tournament. OMaker wins if the tournament has some property PP and OBreaker wins otherwise.We provide 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 HH-creation game, where OMaker wins if the obtained tournament has a copy of some fixed digraph HH.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,