کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423895 | 1632593 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fast embedding of spanning trees in biased Maker-Breaker games
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given a tree T=(V,E) on n vertices, we consider the (1:q) Maker-Breaker tree embedding game Tn. The board of this game is the edge set of the complete graph on n vertices. Maker wins Tn if and only if he is able to claim all edges of a copy of T. We prove that there exist real numbers α,ε>0 such that, for sufficiently large n and for every tree T on n vertices with maximum degree at most nε, Maker has a winning strategy for the (1:q) game Tn, for every q⩽nα. Moreover, we prove that Maker can win this game within n+o(n) moves which is clearly asymptotically optimal.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 331-336
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 331-336
نویسندگان
Dan Hefetz, Asaf Ferber, Michael Krivelevich,