ملخص
Given a tree T=(V, E) on n vertices, we consider the (1:q) Maker-Breaker tree embedding game T n. The board of this game is the edge set of the complete graph on n vertices. Maker wins Tn if and only if she 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.
| اللغة الأصلية | الإنجليزيّة |
|---|---|
| الصفحات (من إلى) | 1086-1099 |
| عدد الصفحات | 14 |
| دورية | European Journal of Combinatorics |
| مستوى الصوت | 33 |
| رقم الإصدار | 6 |
| المعرِّفات الرقمية للأشياء | |
| حالة النشر | نُشِر - أغسطس 2012 |
| منشور خارجيًا | نعم |
بصمة
أدرس بدقة موضوعات البحث “Fast embedding of spanning trees in biased Maker-Breaker games'. فهما يشكلان معًا بصمة فريدة.قم بذكر هذا
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver