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: | Clemens, Dennis, Ferber, Asaf, Glebov, Roman, Hefetz, Dan, Liebenau, Anita |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Mathematics |
Format: | Article |
Language: | en_US |
Published: |
Society for Industrial and Applied Mathematics
2015
|
Online Access: | http://hdl.handle.net/1721.1/100546 |
Similar Items
-
Maker-Breaker domination game on trees when Staller wins
by: Csilla Bujtás, et al.
Published: (2023-09-01) -
Fast strategies in biased Maker--Breaker games
by: Mirjana Mikalački, et al.
Published: (2018-10-01) -
Maker-Breaker total domination game on cubic graphs
by: Jovana Forcan, et al.
Published: (2022-06-01) -
Statins: antimicrobial resistance breakers or makers?
by: Humphrey H.T. Ko, et al.
Published: (2017-10-01) -
TCR Recognition of Peptide–MHC-I: Rule Makers and Breakers
by: Christopher Szeto, et al.
Published: (2020-12-01)