Building spanning trees quickly in maker-breaker games

Dennis Clemens, Asaf Ferber, Roman Glebov, Dan Hefetz, Anita Liebenau

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

8 اقتباسات (Scopus)

ملخص

For a tree T on n vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on n vertices, which Maker wins as soon as the graph she builds contains a copy of T. We prove that if T has bounded maximum degree and n is sufficiently large, then Maker can win this game within n + 1 moves. Moreover, we prove that Maker can build almost every tree on n vertices in nâ'1 moves and provide nontrivial examples of families of trees which Maker cannot build in n â'1 moves.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)1683-1705
عدد الصفحات23
دوريةSIAM Journal on Discrete Mathematics
مستوى الصوت29
رقم الإصدار3
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2015
منشور خارجيًانعم

بصمة

أدرس بدقة موضوعات البحث “Building spanning trees quickly in maker-breaker games'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا