Article in volume
Authors:
Title:
The graph grabbing game on blow-ups of trees and cycles
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 895-907
Received: 2020-12-07 , Revised: 2021-04-25 , Accepted: 2021-05-05 , Available online: 2021-06-24 , https://doi.org/10.7151/dmgt.2410
Abstract:
The graph grabbing game is played on a non-negatively weighted connected graph
by Alice and Bob who alternately claim a non-cut vertex from the remaining graph,
where Alice plays first, to maximize the weights on their respective claimed
vertices at the end of the game when all vertices have been claimed. Seacrest
and Seacrest conjectured that Alice can secure at least half of the total weight
of every weighted connected bipartite even graph. Later, Egawa, Enomoto and
Matsumoto partially confirmed this conjecture by showing that Alice wins the
game on a class of weighted connected bipartite even graphs called
$K_{m,n}$-trees. We extend the result on this class to include a number of
graphs, e.g. even blow-ups of trees and cycles.
Keywords:
games on graphs, two-player games, graph grabbing games, blow-ups of graphs
References:
- S. Chaplick, P. Micek, T. Ueckerdt and V. Wiechert, A note on concurrent graph sharing games, Integers 16 (2016) #G1.
- J. Cibulka, J. Kynčl, V. Mészáros, R. Stolař, and P. Valtr, Graph sharing games: complexity and connectivity, Theoret. Comput. Sci. 494 (2013) 49–62.
https://doi.org/10.1016/j.tcs.2012.12.029 - Y. Egawa, H. Enomoto and N. Matsumoto, The graph grabbing game on {$K_{m,n}$}-trees, Discrete Math. 341 (2018) 1555–1560.
https://doi.org/10.1016/j.disc.2018.02.023 - S. Eoh and J. Choi, The graph grabbing game on $\{0, 1\}$-weighted graphs, Results Appl. Math. 3 (2019) # 100028.
https://doi.org/10.1016/j.rinam.2019.100028 - A. Gągol, P. Micek and B. Walczak, Graph sharing game and the structure of weighted graphs with a forbidden subdivision, J. Graph Theory 85 (2017) 22–50.
https://doi.org/10.1002/jgt.22045 - K. Knauer, P. Micek and T. Ueckerdt, How to eat $4/9$ of a pizza, Discrete Math. 311 (2011) 1635–1645.
https://doi.org/10.1016/j.disc.2011.03.015 - N. Matsumoto, T. Nakamigawa and T. Sakuma, Convex grabbing game of the point set on the plane, Graphs Combin. 36 (2020) 51–62.
https://doi.org/10.1007/s00373-019-02117-z - P. Micek and B. Walczak, A graph-grabbing game, Combin. Probab. Comput. 20 (2011) 623–629.
https://doi.org/10.1017/S0963548311000071 - P. Micek and B. Walczak, Parity in graph sharing games, Discrete Math. 312 (2012) 1788–1795.
https://doi.org/10.1016/j.disc.2012.01.037 - M. Rosenfeld, A gold-grabbing game, Open Problem Garden (2009).
http://www.openproblemgarden.org/op/a_gold_grabbing_game - D.E. Seacrest and T. Seacrest, Grabbing the gold, Discrete Math. 312 (2012) 1804–1806.
https://doi.org/10.1016/j.disc.2012.01.010 - P. Winkler, Mathematical Puzzles: A Connoisseur's Collection (A K Peters, Ltd., Natick, MA, 2004).
Close