Os Seminários de Combinatória têm a satisfação em divulgar que a tese da aluna Deise Lilian de Oliveira, da Pós-Graduação em Matemática da UFF, foi selecionada como Menção Honrosa na Categoria Doutorado dos Prêmios da SBMAC.
Os resultados já foram divulgados no portal da sociedade (https://www.sbmac.org.br), no site do CNMAC 2024 (https://cnmac.org.br), e nas respectivas redes sociais.. Vale ressaltar que a tese foi desenvolvida durante o período de pandemia, sob a orientação dos professores Simone Dantas, da UFF, e Atilio Gomes Luiz, da UFC.
Data: 17/07/2024
Horário: 14h
Sala: https://meet.google.com/sqs-etsv-tzi
Palestrante: Deise L. de Oliveira, IFRJ.
Emitiremos certificados de participação para Atividade Complementar. Basta colocar seu nome completo, instituição de origem, e e-mail no Chat ao final do seminário. Não é necessária inscrição prévia.
Título: Results on the Graceful Game and Range-Relaxed Graceful Game on Graphs and new variants of labeling games
Abstract:
Given a graph G=(V,E) and a set of consecutive integer labels $\mathcal{L} \subset \mathbb{Z}_{\geq 0}$, a vertex labeling of G is a function $f: V(G) \longrightarrow \mathcal{L}$ that induces an edge label g(uv) for every edge $uv \in E(G)$. When $\mathcal{L} = \{0,1,\ldots,k\}$, the function f is injective and the label induced on each edge $uv \in E(G)$ is given by $g(uv)=|f(u)-f(v)|$, resulting in all edge labels being distinct, we call the labeling \textit{graceful} if, additionally, $k=|E(G)|$; or Range-Relaxed Graceful}when this condition is relaxed for $k \geq |E(G)|$. If $\mathcal{L} = \{1,2,\ldots,k\}$, 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).
In 2017, 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). We investigate the graceful game on Cartesian and corona products and other classic families of graphs. In addition, we present the first results in the literature on the RRG game, and we prove that Alice wins the RRG game when she starts on any graph G with order n for any set $\mathcal{L}=\left\{0, 1,\ldots, k\right\}$ with $k \geq (n-1)+\frac{\Delta(\Delta-1)}{2}+\max\{d(v)\cdot 2(m-d(v)) \colon v \in V(G)\}$.
Furthermore, 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 $\mathcal{L}=\{0,\ldots, k\}$, independently of which player starts the game.