We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
GRAPH GRABBING GAME ON GRAPHS WITH FORBIDDEN SUBGRAPHS.
- Authors
MASAYOSHI DOKI; YOSHIMI EGAWA; NAOKI MATSUMOTO
- 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.
- Subjects
SUBGRAPHS; GRAPH connectivity; BIPARTITE graphs; GAMES
- Publication
Discussiones Mathematicae: Graph Theory, 2024, Vol 44, Issue 1, p171
- ISSN
1234-3099
- Publication type
Article
- DOI
10.7151/dmgt.2440