Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-06T07:14:25.328Z Has data issue: false hasContentIssue false
  • English
  • Français

A Graph-Grabbing Game

Published online by Cambridge University Press:  09 March 2011

PIOTR MICEK  and
BARTOSZ WALCZAK
PIOTR MICEK
Affiliation:
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)
BARTOSZ WALCZAK
Affiliation:
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)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 4 , July 2011 , pp. 623 - 629
Copyright
Copyright © Cambridge University Press 2011

References

[1]Cibulka, J., Kynčl, J., Mészáros, V., Stolař, R. and Valtr, P. (2009) Solution to Peter Winkler's pizza problem. In Combinatorial Algorithms (Fiala, J., Kratochvíl, J. and Miller, M., eds), Vol. 5874 of Lecture Notes in Computer Science, Springer, pp. 356–367.CrossRefGoogle Scholar
[2]Cibulka, J., Kynčl, J., Mészáros, V., Stolař, R. and Valtr, P. (2010) Graph sharing games: Complexity and connectivity. In Theory and Applications of Models of Computation (Kratochvíl, J., Li, A., Fiala, J. and Kolman, P., eds), Vol. 6108 of Lecture Notes in Computer Science, Springer, pp. 340–349.CrossRefGoogle Scholar
[3]Knauer, K., Micek, P. and Ueckerdt, T. How to eat $\frac{4}{9}$ of a pizza. Discrete Mathematics, to appear.Google Scholar
[4]Micek, P. and Walczak, B. Parity in graph sharing games. Submitted.Google Scholar
[5]Rosenfeld, M. A gold-grabbing game. Open Problem Garden: http://garden.irmacs.sfu.ca/?q=op/a_gold_grabbing_game.Google Scholar
[6]Winkler, P. M. (2008) Problem posed at Building Bridges, a conference in honour of the 60th birthday of László Lovász, Budapest.Google Scholar
[7]Winkler, P. M. (2004) Mathematical Puzzles: A Connoisseur's Collection, A. K. Peters.Google Scholar