Building Spanning Trees Quickly in Maker-Breaker Games
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 wi...
Main Authors: | , , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | en_US |
Published: |
Society for Industrial and Applied Mathematics
2015
|
Online Access: | http://hdl.handle.net/1721.1/100546 |