论文标题
在优雅的游戏中
On the Graceful Game
论文作者
论文摘要
图形$ g $具有$ m $边缘的优美标签包括标记$ g $的顶点，并具有不同的整数从$ 0 $到$ m $，这样，当将每个边缘分配为诱导的标签时，所有诱导的边缘标签的标签的绝对差异都不同。罗莎（Rosa）建立了两个众所周知的猜想：所有树木都是优雅的（1966年），所有三角仙人掌都优雅（1988）。为了为这两个猜想做出贡献，我们在图形游戏的背景下研究优雅的标签。 Tuza在2017年作为两人游戏在连接的图上引入了优雅的游戏，玩家爱丽丝和鲍勃轮流以0至$ m $的不同整数标记顶点。爱丽丝的目标是优雅地将图形标记为鲍勃的目标是防止其发生。在这项工作中，我们在完整的图形，路径，周期，完整的二分图，毛毛虫，棱镜，车轮，头盔，网络，齿轮图，齿轮图，超振管和某些路径的力量中研究了爱丽丝和鲍勃的获胜策略。
A graceful labeling of a graph $G$ with $m$ edges consists of labeling the vertices of $G$ with distinct integers from $0$ to $m$ such that, when each edge is assigned as induced label the absolute difference of the labels of its endpoints, all induced edge labels are distinct. Rosa established two well known conjectures: all trees are graceful (1966) and all triangular cacti are graceful (1988). In order to contribute to both conjectures we study graceful labelings in the context of graph games. The Graceful game was introduced by Tuza in 2017 as a two-players game on a connected graph in which the players Alice and Bob take turns labeling the vertices with distinct integers from 0 to $m$. Alice's goal is to gracefully label the graph as Bob's goal is to prevent it from happening. In this work, we study winning strategies for Alice and Bob in complete graphs, paths, cycles, complete bipartite graphs, caterpillars, prisms, wheels, helms, webs, gear graphs, hypercubes and some powers of paths.
