On the Graceful Game
Abstract
A graceful labeling of a graph G with m edges consists in labeling the vertices of G with distinct integers from 0 to m such that, when each edge is assigned 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 these problems 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 present the first results in this area by showing 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.
References
Ayel, J. and Favaron, O. (1984). Helms are graceful. in Progress in Graph Theory (Waterloo, Ont., 1982), Academic Press, Toronto, Ont., pages 89–92.
Berlekamp, E. R., Conway, J. H., and Guy, R. K. (1982). Winning ways for your mathematical plays. Academic Press.
Frickes, L., Dantas, S., and Luiz, A. G. (2019). The graceful game. In Proceedings of 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2019), volume 1, pages 41–44.
Frucht, R. (1979). Graceful numbering of wheels and related graphs. Annals of the New York Academy of Sciences, 319(1):219–229.
Frucht, R. and Gallian, J. A. (1988). Labeling prisms. Ars Combinatoria, 26:69–82.
Golomb, S.W. (1972). How to number a graph. In Read, R. C., editor, Graph Theory and Computing, pages 23–37. Academic Press, New York.
Harary, F., Hayes, J. P., andWu, H.-J. (1988). A survey of the theory of hypercube graphs. Computers & Mathematics with Applications, 15(4):277–289.
Hoede, C. and Kuiper, H. (1987). All wheels are graceful. Utilitas Mathematica, 14:311.
Kang, Q., Liang, Z.-H., Gao, Y.-Z., and Yang, G.-H. (1996). On labeling of some graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 22:193–210.
Kho, K. M., Rogers, D. G., Teo, H. K., and Yap, K. Y. (1980). Graceful graphs: some further results and problems. Congressus Numerantium, 29:559–571.
Kotzig, A. (1981). Decompositions of complete graphs into isomorphic cubes. Journal of Combinatorial Theory, B 31:292–2496.
Ma, K. J. and Feng, C. J. (1984). On the gracefulness of gear graphs. Mathematics in Practice and Theory, pages 72–73.
Rosa, A. (1967). On certain valuations of the vertices of a graph. Theory of Graphs, International Symposium, Rome, July 1966, pages 349–355.
Rosa, A. (1988). Cyclic steiner triple systems and labelings of triangular cacti. Scientia, 1:87–95.
Tuza, Z. (2017). Graph labeling games. Electronic Notes in Discrete Mathematics, 60:61–68.
