Range-Relaxed Graceful Game

Speaker: Deise L. de Oliveira, UFF.

Date: 26 aug 2020, 16h.

Place: Google Meet: meet.google.com/ces-qqwf-coo.

Abstract: The Range-Relaxed Graceful Game is played in a simple graph G, by two players, Alice and Bob, who alternately assign a previously unused label f(v) \in £={0, ..., k}, k >=|E(G)|, to a previously unlabeled vertex v \in V(G). Alice's goal is to end up with a vertex labeling of whole G where all of its edges have distinct labels and Bob's goal is to prevent it from happening. When k=|E(G)|, it is called Graceful game. We investigate the graceful game in cartesian and corona products of graphs, and determine that Bob has a winning strategy in all investigated families independently of who starts the game. Additionally, we present the first results in the range-relaxed graceful game.

Obs.: This joint work with Simone Dantas (IME-UFF) and Atílio G. Luiz (UFC), was accepted for presentation and publication in the CTW 2020 (18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization).