TY - JOUR

T1 - Graph grabbing game on totally-weighted graphs

AU - Matsumoto, Naoki

AU - Moriyama, Ryusei

AU - Ota, Katsuhiro

N1 - Funding Information:
Supported by JSPS Grant-in-Aid for Early-Career Scientists19K14583.
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/12/15

Y1 - 2022/12/15

N2 - The graph grabbing game is a two-player game on a connected graph with a vertex-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. In this paper, we consider the graph grabbing game on totally-weighted graphs that are graphs with weight functions from a set of elements in the vertex set and the edge set to non-negative real numbers. In this version, when a player removes a non-cut vertex v, that player gets the weight of v plus the total weight assigned to the edges incident to v. In particular, we give some results of interest for the graph grabbing game on edge-weighted trees, i.e., every vertex has weight zero. Moreover, we consider the game on edge-weighed graphs in the altered rule that each player must keep the connectedness of graphs induced by edges.

AB - The graph grabbing game is a two-player game on a connected graph with a vertex-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. In this paper, we consider the graph grabbing game on totally-weighted graphs that are graphs with weight functions from a set of elements in the vertex set and the edge set to non-negative real numbers. In this version, when a player removes a non-cut vertex v, that player gets the weight of v plus the total weight assigned to the edges incident to v. In particular, we give some results of interest for the graph grabbing game on edge-weighted trees, i.e., every vertex has weight zero. Moreover, we consider the game on edge-weighed graphs in the altered rule that each player must keep the connectedness of graphs induced by edges.

KW - Edge-weighted graph

KW - Graph grabbing game

KW - Totally-weighted graph

KW - Tree

UR - http://www.scopus.com/inward/record.url?scp=85138481428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85138481428&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2022.09.007

DO - 10.1016/j.dam.2022.09.007

M3 - Article

AN - SCOPUS:85138481428

SN - 0166-218X

VL - 322

SP - 384

EP - 390

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -