{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:21:43Z","timestamp":1787322103380,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/140976054","type":"journal-article","created":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T11:23:45Z","timestamp":1442316225000},"page":"1683-1705","source":"Crossref","is-referenced-by-count":8,"title":["Building Spanning Trees Quickly in Maker-Breaker Games"],"prefix":"10.1137","volume":"29","author":[{"given":"Dennis","family":"Clemens","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Asaf","family":"Ferber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roman","family":"Glebov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Hefetz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anita","family":"Liebenau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,9,15]]},"reference":[{"key":"atypb1","first-page":"18","author":"Alon N.","year":"2011","journal-title":"Electron. J. Combin."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000936"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00224-2"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"J. Beck,\n                      Combinatorial Games: Tic-Tac-Toe Theory\n                      , Cambridge University Press, Cambridge, UK, 2008.","DOI":"10.1017\/CBO9780511735202"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003708"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70335-2"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000375"},{"key":"atypb8","first-page":"18","author":"Ferber A.","year":"2011","journal-title":"Electron. J. Combin."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.015"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.01.007"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.07.005"},{"key":"atypb12","first-page":"601","author":"Hajnal A.","year":"1970","journal-title":"London"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"D. Hefetz, M. Krivelevich, M. Stojakovic\u0301, and T. Szabo\u0301,\n                      Positional Games\n                      , Birkha\u0308user, Basel, 2014.","DOI":"10.1007\/978-3-0348-0825-5"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.04.001"},{"key":"atypb15","first-page":"16","author":"Hefetz D.","year":"2009","journal-title":"Electron. J. Combin."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"D. Johannsen, M. Krivelevich, and W. Samotij,\n                      Expanders are universal for the class of all spanning trees\n                      , in Proceedings of the 23rd Symposium on Discrete Algorithms (SODA'12), 2012, pp. 1539-1551.","DOI":"10.1137\/1.9781611973099.122"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001620"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/100805753"},{"key":"atypb19","unstructured":"R. Montgomery,\n                      Embedding bounded degree spanning trees in random graphs,\n                      preprint, arXiv:1405.6559 [math.CO], 2014."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1029000098"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300002030"},{"key":"atypb22","unstructured":"D. B. West,\n                      Introduction to Graph Theory\n                      , Prentice-Hall, Englewood Cliff, NJ, 2001."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140976054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:13Z","timestamp":1787318293000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140976054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140976054"],"URL":"https:\/\/doi.org\/10.1137\/140976054","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}