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

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Building spanning trees quickly in maker-breaker games'. יחד הם יוצרים טביעת אצבע ייחודית.

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