Graceful game on some graph classes

¹ IME, Universidade Federal Fluminense, Niterói, RJ, Brazil
² RIC, Universidade Federal Fluminense, Rio das Ostras, RJ, Brazil
³ Campus Quixadá, Universidade Federal do Ceará, Quixadá, CE, Brazil

^* Corresponding author: gomes.atilio@ufc.br

Received: 9 December 2022
Accepted: 8 October 2023

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 each edge is uniquely identified by the absolute difference of the labels of its endpoints. In this work, we study the graceful labeling problem in the context of maker-breaker 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 moves labeling the vertices with distinct integers from 0 to m. Players are constrained to use only legal labelings (moves), that is, after a move, all edge labels are distinct. Alice’s goal is to obtain a graceful labeling for the graph, as Bob’s goal is to prevent it from happening. In this work, we study winning strategies for Alice and Bob in graph classes: paths, complete graphs, cycles, complete bipartite graphs, caterpillars, trees, gear graphs, web graphs, prisms, hypercubes, 2-powers of paths, wheels and fan graphs.