ملخص
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'. فهما يشكلان معًا بصمة فريدة.قم بذكر هذا
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver