Navegar por:

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

Use este link compartilhar ou citar este material: http://educapes.capes.gov.br/handle/capes/766361
Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSouza, Simone Dantas de-
Autor(es): dc.contributorLuiz, Atílio Gomes-
Autor(es): dc.creatorOliveira, Deise Lilian de-
Data de aceite: dc.date.accessioned2024-07-11T18:14:04Z-
Data de disponibilização: dc.date.available2024-07-11T18:14:04Z-
Data de envio: dc.date.issued2024-07-05-
Data de envio: dc.date.issued2024-07-05-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/33037-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/766361-
Descrição: dc.descriptionGiven 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-
Descrição: dc.descriptionDado um grafo G = (V,E) e um conjunto de rótulos inteiros consecutivos L = {0, . . . , k}, uma rotulação de vértices de G é uma função f : V (G) −→ L que induz uma rotulação de arestas g(uv) para toda aresta uv ∈ E(G). Quando a função f é injetiva e o rótulo induzido em cada aresta uv ∈ E(G) é dado por g(uv) = |f (u) − f (v)|, resultando em todos os rótulos de arestas distintos, chamamos a rotulação f de graceful, se adicionalmente, k = |E(G)|, ou Range-Relaxed Graceful (RRG) quando essa condição é relaxada, ou seja, k ≥ |E(G)|. Desde 1963, muitas rotulações de grafos baseadas em somas de rótulos inteiros foram propostas. Assim, se a rotulação de vértices f é injetiva e o rótulo induzido nas arestas é dado por g(uv) = f (u) + f (v), então a rotulação é chamada de Edge-Sum Distinguishing (ESD). Uma outra maneira de abordar o tema de rotulação é através de jogos combinatórios. Em 2017, Tuza publicou um artigo enfatizando que apesar da rotulação de grafos ser uma área vasta de trabalho, com diversos problemas em aberto, pouco havia sido feito em jogos combinatórios até o momento. Tuza propôs o estudo de novos jogos maker-breaker tais como o jogo graceful, o jogo Range-Relaxed Graceful (RRG) e o jogo Edge-Sum Distinguishing (ESD). Nesses jogos, Alice e Bob atribuem alternadamente um rótulo (respeitando as regras da rotulação que está sendo construída) não usado a um vértice não rotulado. O objetivo da Alice é terminar o jogo com uma rotulação de vértices de G e o objetivo do Bob é impedir que isso aconteça. Tuza também formulou as seguintes questões sobre os jogos de rotulação: dado um grafo simples G e um inteiro k, que indica o valor máximo do conjunto de rótulos inteiros consecutivos, para quais valores de k Alice pode vencer o jogo? E se Alice vencer o jogo com o conjunto de rótulos até k, ela também poderá ganhar com rótulos até k + 1? Nesse trabalho, respondemos a essas questões para os jogos graceful, RRG e ESD, apresentando limites para o número de rótulos inteiros consecutivos não negativos L = {0, . . . , k} necessários para Alice vencer o jogo em famílias clássicas de grafos. Investigamos o jogo graceful em produtos Cartesiano e produto corona de grafos. Adicionalmente, apresentamos os primeiros resultados na literatura sobre o jogo RRG, e provamos que Alice vence em qualquer grafo G com ordem n para ∆(∆−1) qualquer conjunto L = {0, 1, . . . , k} com k ≥ (n − 1) + max{d(v) · 2(m − d(v)) : v ∈ 2 V (G)}, respondendo de modo afirmativo às duas questões colocadas por Tuza. Além disso, apresentamos limites para o número do jogo ESD, que é o mínimo número inteiro não negativo k tal que Alice tem uma estratégia vencedora jogando em um grafo G com um conjunto de rótulos L = {0, . . . , k}, independentemente de qual jogador inicia o jogo.-
Descrição: dc.description81 f.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectgraph labeling-
Palavras-chave: dc.subjectlabeling games-
Palavras-chave: dc.subjectJogo em Educação Matemática-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectrotulação de grafos-
Palavras-chave: dc.subjectjogos de rotulação-
Título: dc.titleResults on the graceful game and range-relaxed graceful Game on graphs and new variants of labeling games-
Tipo de arquivo: dc.typeTese-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.
Mostrar registro simples do item Visualizar estatísticas

Avaliação