Article ID Journal Published Year Pages File Type
4646954 Discrete Mathematics 2015 7 Pages PDF
Abstract
We consider the weighted version of the Tron game on graphs where two players, Alice and Bob, each build their own path by claiming one vertex at a time, starting with Alice. The vertices carry non-negative weights that sum up to 1 and either player tries to claim a path with larger total weight than the opponent. We show that if the graph is a tree then Alice can always ensure she receives 1/5 less than Bob or better, and this is best possible.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,