21 dez 2023
14:00 Defesa de Mestrado Auditório do IC3
Tema
Rotulação L(h, k) em classes de grafos
Aluno
João Paulo Kubaszewski Castilho
Orientador / Docente
Christiane Neme Campos - Coorientador: Leandro Miranda Zatesko
Breve resumo
Este trabalho insere-se no contexto de Teoria de Grafos, tendo como foco o problema de rotulação L(h, k), que consiste em atribuir valores – denominados rótulos – inteiros aos vértices de um grafo simples, de modo que vértices adjacentes recebam rótulos que difiram em pelo menos h e vértices que possuem um vizinho em comum recebam rótulos que difiram em pelo menos k. O span de uma rotulação σ é a diferença absoluta entre o maior e o menor rótulo de σ . Dizemos que a rotulação σ é ótima para um grafo G se essa diferença é a menor possível. Esse valor é denominado L(h, k)-span e é denotado λh,k (G). Esse problema é uma generalização proposta por J. P. Georges e D. W. Mauro do problema de rotulação L (2, 1), introduzido por F. S. Roberts, J. R. Griggs, e R. K. Yeh como uma solução para o Problema de Atribuição de canais. Determinar se uma rotulação L (h, k) é ótima para um grafo foi provado ser NP-difícil, mesmo quando restrito a algumas classes de grafos, como árvores.
Nesta dissertação, determinados o L(h, k)-span para as seguintes classes de grafos: caterpillars uniformes, sunlets, multisunlets uniformes, e caterpillars não-uniformes com diâmetro limitado a seis. Além disso, estabelecemos algumas condições necessárias que toda rotulação L(h, k) de uma estrela deve seguir. Neste trabalho, essas condições são aplicadas diretamente nas classes estudadas.
Banca examinadora
Titulares:
| Christiane Neme Campos | IC/UNICAMP |
| Luerbio Faria | UERJ |
| Orlando Lee | IC/UNICAMP |
Suplentes:
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Rosiane de Freitas Rodrigues | UFAM |