Article in volume
Authors:
Title:
Graph grabbing game on graphs with forbidden subgraphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 171-197
Received: 2020-09-30 , Revised: 2021-11-07 , Accepted: 2021-11-08 , Available online: 2021-11-22 , https://doi.org/10.7151/dmgt.2440
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:
graph grabbing game, forbidden subgraph, corona product
References:
- S. Chaplick, P. Micek, T. Ueckerdt and V. Wiechert, A note on concurrent graph sharing games, Integers 16 (2016) #G1.
- V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
https://doi.org/10.1016/0012-365X(73)90138-6 - 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 - 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 - 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 - 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.
- 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. 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 - P. van't Hof and D. Paulusma, A new characterization of $P_6$-free graphs, Discrete Appl. Math. 158 (2010) 731–740.
https://doi.org/10.1016/j.dam.2008.08.025 - 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 - 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 - 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 - M.M. Matthews and D.P. Sumner, Hamiltonian results in $K_{1,3}$-free graphs, J. Graph Theory 8 (1984) 139–146.
https://doi.org/10.1002/jgt.3190080116 - 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 - 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 - 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 - P.M. Winkler, Mathematical Puzzles: A Connoisseur's Collection (A K Peters/CRC Press, New York, 2003).
https://doi.org/10.1201/b16493
Close