תקציר
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.
| שפה מקורית | אנגלית |
|---|---|
| עמודים (מ-עד) | 331-336 |
| מספר עמודים | 6 |
| כתב עת | Electronic Notes in Discrete Mathematics |
| כרך | 38 |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - 1 דצמ׳ 2011 |
| פורסם באופן חיצוני | כן |
טביעת אצבע
להלן מוצגים תחומי המחקר של הפרסום 'Fast embedding of spanning trees in biased Maker-Breaker games'. יחד הם יוצרים טביעת אצבע ייחודית.פורמט ציטוט ביבליוגרפי
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver