On the Graceful Game
From MaRDI portal
Publication:6340465
arXiv2005.05213MaRDI QIDQ6340465FDOQ6340465
Authors: Simone Dantas, Atílio G. Luiz 
Publication date: 11 May 2020
Abstract: A graceful labeling of a graph with edges consists of labeling the vertices of with distinct integers from to 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 . 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.
Games on graphs (graph-theoretic aspects) (05C57) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Games involving graphs (91A43) Combinatorial games (91A46)
This page was built for publication: On the Graceful Game
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340465)
