Geodesic
Graph grabbing game on graphs with forbidden subgraphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 171-197 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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: graph grabbing game, forbidden subgraph, corona product 
@article{DMGT_2024_44_1_a8,
     author = {Doki, Masayoshi and Egawa, Yoshimi and Matsumoto, Naoki},
     title = {Graph grabbing game on graphs with forbidden subgraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {171--197},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a8/}
}
TY  - JOUR
AU  - Doki, Masayoshi
AU  - Egawa, Yoshimi
AU  - Matsumoto, Naoki
TI  - Graph grabbing game on graphs with forbidden subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 171
EP  - 197
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a8/
LA  - en
ID  - DMGT_2024_44_1_a8
ER  - 
%0 Journal Article
%A Doki, Masayoshi
%A Egawa, Yoshimi
%A Matsumoto, Naoki
%T Graph grabbing game on graphs with forbidden subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 171-197
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a8/
%G en
%F DMGT_2024_44_1_a8
Doki, Masayoshi; Egawa, Yoshimi; Matsumoto, Naoki. Graph grabbing game on graphs with forbidden subgraphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 171-197. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a8/

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

[2] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. https://doi.org/10.1016/0012-365X(73)90138-6

[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.029

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

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

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

[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.023

[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.100028

[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.22045

[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.025

[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.022

[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.015

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

[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.3190080116

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

[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.037

[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.010

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

[19] P.M. Winkler, Mathematical Puzzles: A Connoisseur's Collection (A K Peters/CRC Press, New York, 2003). https://doi.org/10.1201/b16493