1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Graph Grabbing Game on Blow-ups of Trees and Cycles

Published Online: 17 Jun 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 07 Dec 2020
Accepted: 05 May 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 Km,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

MSC 2010

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

[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.02910.1016/j.tcs.2012.12.029Search in Google Scholar

[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.02310.1016/j.disc.2018.02.023Search in Google Scholar

[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.10002810.1016/j.rinam.2019.100028Search in Google Scholar

[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.2204510.1002/jgt.22045Search in Google Scholar

[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.01510.1016/j.disc.2011.03.015Search in Google Scholar

[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-z10.1007/s00373-019-02117-zSearch in Google Scholar

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

[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.03710.1016/j.disc.2012.01.037Search in Google Scholar

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

[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.01010.1016/j.disc.2012.01.010Search in Google Scholar

[12] P. Winkler, Mathematical Puzzles: A Connoisseur’s Collection (A K Peters, Ltd., Natick, MA, 2004).Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo