21dez2023
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
Instituto de Computação
Privacy Overview

This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.