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

Graph Grabbing Game on Graphs with Forbidden Subgraphs

Published Online: 26 Nov 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 30 Sep 2020
Accepted: 08 Nov 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 a two-player game on a connected graph with a weight function. In the game, they alternately remove a non-cut vertex from the graph (i.e., the resulting graph remains connected) and get the weight assigned to the vertex. Each player’s aim is to maximize his or her outcome, when all vertices have been taken. Seacrest and Seacrest proved that if a given graph G is a tree with even order, then the first player can win the game for every weight function on G, and conjectured that the same statement holds if G is a connected bipartite graph with even order [D.E. Seacrest and T. Seacrest, Grabbing the gold, Discrete Math. 312 (2012) 1804–1806]. In this paper, we introduce a conjecture which is stated in terms of forbidden subgraphs and includes the above conjecture, and give two partial solutions to the conjecture.

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] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. https://doi.org/10.1016/0012-365X(73)90138-610.1016/0012-365X(73)90138-6 Search in Google Scholar

[3] 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.029 Search in Google Scholar

[4] J. Cibulka, R. Stolař, J. Kynčl, V. Mészáros and P. Valtr, Solution to Peter Winkler’s pizza problem, in: Fete of Combinatorics and Computer Science, Bolyai Soc. Math. Stud. 20 (Springer, Berlin, 2010) 63–93. https://doi.org/10.1007/978-3-642-13580-4_410.1007/978-3-642-13580-4_4 Search in Google Scholar

[5] R. Diestel, Graph Theory, Fifth Edition, in: Grad. Texts in Math. 173 (Springer, Berlin, Heidelberg, 2017). https://doi.org/10.1007/978-3-662-53622-310.1007/978-3-662-53622-3 Search in Google Scholar

[6] D. Duffus, R.J. Gould and M.S. Jacobson, Forbidden subgraphs and the Hamiltonian theme, in: The Theory and Applications of Graphs (Wiley, New York, 1981) 297–316. Search in Google Scholar

[7] 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.023 Search in Google Scholar

[8] 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.100028 Search in Google Scholar

[9] A. Gagol, 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.22045 Search in Google Scholar

[10] P. van’t Hof and D. Paulusma, A new characterization of P6-free graphs, Discrete Appl. Math. 158 (2010) 731–740. https://doi.org/10.1016/j.dam.2008.08.02510.1016/j.dam.2008.08.025 Search in Google Scholar

[11] A. Kelmans, On Hamiltonicity of {claw, net}-free graphs, Discrete Math. 306 (2006) 2755–2761. https://doi.org/10.1016/j.disc.2006.04.02210.1016/j.disc.2006.04.022 Search in Google Scholar

[12] 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.015 Search in Google Scholar

[13] J. Liu and H. Zhou, Dominating subgraphs in graphs with some forbidden structures, Discrete Math. 135 (1994) 163–168. https://doi.org/10.1016/0012-365X(93)E0111-G10.1016/0012-365X(93)E0111-G Search in Google Scholar

[14] M.M. Matthews and D.P. Sumner, Hamiltonian results in K1,3-free graphs, J. Graph Theory 8 (1984) 139–146. https://doi.org/10.1002/jgt.319008011610.1002/jgt.3190080116 Search in Google Scholar

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

[16] 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.037 Search in Google Scholar

[17] 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.010 Search in Google Scholar

[18] F.B. Shepherd, Hamiltonicity in claw-free graphs, J. Combin. Theory Ser. B 53 (1991) 173–194. https://doi.org/10.1016/0095-8956(91)90074-T10.1016/0095-8956(91)90074-T Search in Google Scholar

[19] P.M. Winkler, Mathematical Puzzles: A Connoisseur’s Collection (A K Peters/CRC Press, New York, 2003). https://doi.org/10.1201/b1649310.1201/b16493 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo