Results on the graceful game and range-relaxed graceful Game on graphs and new variants of labeling games

• Ano de defesa: 2024
• Autor(a) principal: Oliveira, Deise Lilian de
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: graph labeling; labeling games; Jogo em Educação Matemática; Grafo; rotulação de grafos; jogos de rotulação
• Link de acesso: https://app.uff.br/riuff/handle/1/33037

Given a graph G = (V, E) and a set of consecutive integer labels L = {0, . . . , k}, a vertex labeling of G is a function f : V (G) −→ L that induces an edge labeling g(uv) for every edge uv ∈ E(G). When the function f is injective and the label induced on each edge uv ∈ E(G) is given by g(uv) = |f(u) − f(v)|, resulting in all edge labels being distinct, we call the labeling graceful, if additionally, k = |E(G)| or Range-Relaxed Graceful when this condition is relaxed, that is, k ≥ |E(G)|. Since 1963, many graph labelings based on sums of integer labels have been proposed. Thus, if the vertex labeling f is injective and the label induced on the edges is given by g(uv) = f(u) + f(v), then the labeling is called Edge-Sum Distinguishing (ESD). Another way to approach the topic of graph labeling is through combinatorial games. In 2017, Tuza published an article emphasizing that despite the graph labeling area being a vast area of work, with several open problems, little had been done in combinatorial games so far. Tuza proposed the study of new maker-breaker games such as the graceful game, the Range-Relaxed Graceful game (RRG game) and the Edge-Sum Distinguishing game (ESD game). In these games, Alice and Bob alternately assign an unused label (respecting the rules of the labeling that is being constructed) to a vertex not labeled. Alice’s goal is to finish the game with a vertex labeling of G and Bob’s goal is to prevent this from happening. Tuza also posed the following questions about the labeling games: given a simple graph G and an integer k, indicating the maximum value of the set of consecutive integer labels, for which values of k can Alice win the game? And if Alice wins the game with the set of labels up to k, can she also win with labels up to k + 1? In this work, we partially answer these questions for the graceful game, RRG game and ESD game, by presenting limits to the number of consecutive nonnegative integer labels L = {0, . . . , k} needed for Alice to win the game on classic families of graph. We investigate the graceful game on Cartesian products and corona products. In addition, we present the first results in the literature on the RRG game, and we proved that Alice wins on any graph G with order n for any set L = {0, 1, . . . , k} with k ≥ (n − 1) + ∆(∆−1) 2 + max{d(v) · 2(m − d(v)): v ∈ V (G)}, which gives affirmative answers for the two questions posed by Tuza. Futhermore, we present bounds for the ESD game number, that is the minimum nonnegative integer k such that Alice has a winning strategy playing the ESD game on G with a set of labels L = {0, . . . , k}, independently of which player starts the gam