Parity in graph sharing games
Parity in graph sharing games
复制标题
图共享游戏中的奇偶校验
DOI：
10.1016/j.disc.2012.01.037
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Bartosz Walczak
中科院分区：
文献类型：
--
作者：
Piotr Micek;Bartosz Walczak
两个玩家共享一个顶点权重为非负的连通图。他们交替地逐一获取顶点并收集它们的权重。他们必须遵守的规则是，每次移动后，图形的截取部分必须连接起来。我们提出了一种策略，让第一个玩家获得至少 1/4 的具有奇数个顶点的树。奇偶条件是必要的：很容易找到第一个玩家的保证结果趋于零的偶数树。一般来说，有一些奇怪的图表，第一个玩家的结果是任意小的，但所有已知的结构都是复杂的。我们怀疑存在一种普遍的奇偶现象，即第一个玩家可以确保任何具有奇数个顶点的无 Kn 小图的大部分权重。我们讨论与该游戏的另一种变体的类比，称为图形抓取游戏，其中玩家必须始终保持剩余（未采取）的部分连接。
Two players share a connected graph with non-negative weights on the vertices. They alternately take the vertices one by one and collect their weights. The rule they have to obey is that the taken part of the graph must be connected after each move. We present a strategy for the first player to get at least 1/4 of a tree with an odd number of vertices. The parity condition is necessary: it is easy to find even trees with the first player’s guaranteed outcome tending to zero. In general there are odd graphs with arbitrarily small outcome of the first player, but all known constructions are intricate. We suspect a kind of general parity phenomenon, namely, that the first player can secure a substantial fraction of the weight of any Kn-minor-free graph with an odd number of vertices. We discuss analogies with another variant of this game, called the graph-grabbing game, where the players have to keep the remaining (not taken) part connected all the time.