A Graph-Grabbing Game
Piotr Micek, Bartosz Walczak · Combinatorics Probability Computing · 2011
Two players share a connected graph with non-negative weights on the vertices. They alternately take the vertices (one in each turn) and collect their weights. The rule they have to obey is that the remaining part of the graph must be connected after each move. We conjecture that the first player can get at least half of the weight of any tree with an even number of vertices. We provide a strategy for the first player to get at least 1/4 of an even tree. Moreover, we confirm the conjecture for subdivided stars. The parity condition is necessary: Alice gets nothing on a three-vertex path with all the weight at the middle. We suspect a kind of general parity phenomenon, namely, that the first player can gather a substantial portion of the weight of any ‘simple enough’ graph with an even number of vertices.