Geodesic
The graph grabbing game on blow-ups of trees and cycles
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 895-907 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 
@article{DMGT_2023_43_4_a1,
     author = {Boriboon, Sopon and Kittipassorn, Teeradej},
     title = {The graph grabbing game on blow-ups of trees and cycles},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {895--907},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a1/}
}
TY  - JOUR
AU  - Boriboon, Sopon
AU  - Kittipassorn, Teeradej
TI  - The graph grabbing game on blow-ups of trees and cycles
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 895
EP  - 907
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a1/
LA  - en
ID  - DMGT_2023_43_4_a1
ER  - 
%0 Journal Article
%A Boriboon, Sopon
%A Kittipassorn, Teeradej
%T The graph grabbing game on blow-ups of trees and cycles
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 895-907
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a1/
%G en
%F DMGT_2023_43_4_a1
Boriboon, Sopon; Kittipassorn, Teeradej. The graph grabbing game on blow-ups of trees and cycles. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 895-907. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a1/

[1] S. Chaplick, P. Micek, T. Ueckerdt and V. Wiechert, A note on concurrent graph sharing games, Integers 16 (2016) #G1.

[2] 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

[3] Y. Egawa, H. Enomoto and N. Matsumoto, The graph grabbing game on {Km,n}-trees, Discrete Math. 341 (2018) 1555–1560. https://doi.org/10.1016/j.disc.2018.02.023

[4] 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

[5] 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

[6] 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

[7] 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

[8] P. Micek and B. Walczak, A graph-grabbing game, Combin. Probab. Comput. 20 (2011) 623–629. https://doi.org/10.1017/S0963548311000071

[9] 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

[10] M. Rosenfeld, A gold-grabbing game, Open Problem Garden (2009). http://www.openproblemgarden.org/op/a_gold_grabbing_game

[11] 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

[12] P. Winkler, Mathematical Puzzles: A Connoisseur's Collection (A K Peters, Ltd., Natick, MA, 2004).