Building Spanning Trees Quickly in Maker-Breaker Games
Dennis Clemens, Asaf Ferber, Roman Glebov, Dan Hefetz, Anita Liebenau · SIAM Journal on Discrete Mathematics · 2015
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.