Combinatorics, Probability and Computing

Paper

A Graph-Grabbing Game

PIOTR MICEKa1 and BARTOSZ WALCZAKa1

a1 Department of Theoretical Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Kraków, Poland (e-mail: Piotr.Micek@tcs.uj.edu.pl, Bartosz.Walczak@tcs.uj.edu.pl, URL: http://tcs.uj.edu.pl/Micek, http://tcs.uj.edu.pl/Walczak)

Abstract

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.

(Received March 10 2010)

(Revised January 06 2011)

(Online publication March 09 2011)