Defesa de Mestrado de Celso Aimbiré Weffort Santos

Título do Trabalho
Proper gap-labellings: on the edge and vertex variants
Candidato(a)
Celso Aimbiré Weffort Santos
Nível
Mestrado
Data
Add to Calender 2018-05-22 00:00:00 2018-05-22 00:00:00 Defesa de Mestrado de Celso Aimbiré Weffort Santos Proper gap-labellings: on the edge and vertex variants Sala 322 IC 3 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00
Local
Sala 322 IC 3
Orientador(a)
Christiane Neme Campos
Banca Examinadora

Condição

Titulares  -  Professores Doutores

Unidade/Instituição

Orientador/Presidente

Christiane Neme Campos

IC/UNICAMP

Membro

Simone Dantas de Souza

IME/UFF

Membro

Flávio Keidi Miyazawa

IC/UNICAMP

Membro

Sheila Morais de Almeida

DAINF/UTFPR

 

Condição

Suplentes  -  Professores Doutores

Unidade/Instituição

Membro Suplente

Lehilton Lelis Chaves Pedrosa

IC/UNICAMP

Resumo
Uma rotulação própria é uma atribuição de valores numéricos aos elementos de um grafo, que podem ser seus vértices, arestas ou ambos, de modo a obter - usando certas funções matemáticas sobre o conjunto de rótulos - uma coloração dos vértices do grafo tal que nenhum par de vértices adjacentes receba a mesma cor. 
 
Este texto aborda o problema da rotulação própria por gap em suas versões de arestas e de vértices. Na versão de arestas, um vértice de grau pelo menos dois tem sua cor definida como a maior diferença, i.e. o maior gap, entre os rótulos de suas arestas incidentes; já na variante de vértices, o gap é definido pela maior diferença entre os rótulos dos seus vértices adjacentes. Para vértices de grau um, sua cor é dada pelo rótulo da sua aresta incidente, no caso da versão de arestas, e pelo rótulo de seu vértice adjacente, no caso da versão de vértices. Finalmente, vértices de grau zero recebem cor um. O menor número de rótulos para o qual um grafo admite uma rotulação própria por gap de arestas (vértices) é chamado edge-gap (vertex-gap) number
 
Neste trabalho, apresentamos um breve histórico das rotulações próprias por gap e os resultados obtidos para as duas versões do problema. Estudamos o edge-gap e o vertex-gap numbers para as famílias de ciclos, coroas, rodas, grafos unicíclicos e algumas classes de snarks. Adicionalmente, na versão de vértices, investigamos a família de grafos cúbicos bipartidos hamiltonianos, desenvolvendo diversas técnicas de rotulação para grafos nesta classe.
 
Em uma abordagem relacionada, provamos resultados de complexidade para a família dos grafos subcúbicos bipartidos. Além disso, demonstramos propriedades estruturais destas rotulações de vértices por gap e estabelecemos limitantes inferiores e superiores justos para o vertex-gap number de grafos arbitrários. Mostramos, ainda, que nem todos os grafos admitem uma rotulação de vértices por gap, exibindo duas famílias infinitas que não admitem tal rotulação. A partir dessas classes, definimos um novo parâmetro chamado de gap-strength, referente ao menor número de arestas que precisam ser removidas de um grafo de modo a obter um novo grafo que é gap-vértice-rotulável. Estabelecemos um limitante superior para o gap-strength de grafos completos e apresentamos evidências de que este valor pode ser um limitante inferior