Building Spanning Trees Quickly in Maker-Breaker Games
Building Spanning Trees Quickly in Maker-Breaker Games
复制标题
在 Maker-Breaker 游戏中快速构建生成树
DOI：
10.1137/140976054
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Anita Liebenau
中科院分区：
文献类型：
--
作者：
Dennis Clemens;Asaf Ferber;Roman Glebov;Dan Hefetz;Anita Liebenau
对于一个树顶点，我们研究了在完全图的顶点的边集上进行的Maker-Breaker博弈，只要Maker构建的图包含一个副本，Maker就会获胜。我们证明了，如果有有界的最大度并且足够大，那么Maker可以在行动中赢得这场博弈。此外，我们还证明了Maker可以建立几乎每一棵树的顶点，并提供了Maker不能建立的树族的非平凡例子。
For a treeonvertices, we study the Maker-Breaker game, played on the edge set of the complete graph onvertices, which Maker wins as soon as the graph she builds contains a copy of. We prove that ifhas bounded maximum degree andis sufficiently large, then Maker can win this game withinmoves. Moreover, we prove that Maker can build almost every tree onvertices inmoves and provide nontrivial examples of families of trees which Maker cannot build inmoves.
登录
查看更多内容
关于派系游戏
DOI：
--
发表时间：
2012
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
Heidi Gebauer
通讯作者：
Heidi Gebauer
DOI：
--
发表时间：
1994
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
J. Beck
通讯作者：
J. Beck
Maker-Breaker 游戏中的快速制胜策略
DOI：
10.1016/j.jctb.2008.04.001
发表时间：
2009
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Dan Hefetz;Michael Krivelevich;Miloš Stojaković;Tibor Szabó
通讯作者：
Tibor Szabó
拉姆齐图游戏的制胜策略
DOI：
--
发表时间：
1995
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
A. Pekec
通讯作者：
A. Pekec
影响因子：
1
作者：
Dan Hefetz;Michael Krivelevich;Tibor Szabó
通讯作者：
Tibor Szabó