کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648101 1342393 2012 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Biased orientation games
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Biased orientation games
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 10, 28 May 2012, Pages 1732–1742
نویسندگان
, , ,