דילוג לניווט ראשי דילוג לחיפוש דילוג לתוכן הראשי

Fast embedding of spanning trees in biased Maker-Breaker games

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

9 ציטוטים ‏(Scopus)

תקציר

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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוג׳ 2012
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Fast embedding of spanning trees in biased Maker-Breaker games'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי