Graph grabbing game on totally-weighted graphs
Graph grabbing game on totally-weighted graphs
复制标题
全加权图上的图抓取游戏
DOI：
10.1016/j.dam.2022.09.007
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
R. Moriyama and K. Ota
中科院分区：
文献类型：
--
作者：
N. Matsumoto;R. Moriyama and K. Ota
图抓取游戏是一种基于带有顶点权重函数的连接图的双人游戏。在游戏中，他们交替地从图形中移除一个未切割的顶点（即，生成的图形保持连接），并将权重分配给该顶点。当所有的顶点都被占领时，每个玩家的目标都是最大化自己的结果。在本文中，我们考虑了全加权图上的图抓取博弈。全加权图是指具有从顶点集和边集的元素集合到非负实数的权函数的图。在这个版本中，当玩家移除一个未切割的顶点v时，该玩家将获得v的权重加上分配给与v相关的边的总权重。特别是，我们在边加权树上给出了一些有趣的图抓取游戏结果，即每个顶点的权重为零。此外，我们考虑了边权图上的博弈，在改变规则下，每个参与者必须保持由边引起的图的连通性。
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 (ie, 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, ie, 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.