Defesa de Doutorado de Atílio Gomes Luiz

Título do Trabalho
Graceful labellings and neighbour-distinguishing labellings of graphs
Candidato(a)
Atilio Gomes Luiz
Nível
Doutorado
Data
Add to Calender 2018-05-21 00:00:00 2018-05-21 00:00:00 Defesa de Doutorado de Atílio Gomes Luiz Graceful labellings and neighbour-distinguishing labellings of graphs Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
15:00
Local
Sala 85 IC 2
Orientador(a)
Christiane Neme Campos
Banca Examinadora

Condição

Titulares  (Professores Doutores)

Unidade/Instituição

Orientador/Presidente

Christiane Neme Campos

IC/UNICAMP

1º Externo à Unicamp

Claudia Linhares Sales

DC/UFC

2º Externo à Unicamp

Daniel Morgato Martin

CMCC/UFABC

1º Interno à Unicamp

Célia Picinin de Mello

IC/UNICAMP

2º Interno à Unicamp

João Meidanis

IC/UNICAMP

 

Condição

Suplentes (Professores Doutores)

Unidade/Instituição

1º Interno à Unicamp

Guilherme Pimentel Telles

IC/UNICAMP

2º Interno à Unicamp

Rafael Crivellari Saliba Schouery

IC/UNICAMP

Externo à Unicamp

José Coelho de Pina Junior

IME/USP

Resumo

Três problemas de rotulação em grafos são investigados nesta tese: a Conjetura das Árvores Graciosas, a Conjetura 1,2,3 e a Conjetura 1,2.

Uma rotulação graciosa de um grafo simples G=(V(G),E(G)) é uma função injetora f de V(G) em {0,...,|E(G)|} tal que {|f(u)-f(v)|: uv em E(G)} = {1,...,|E(G)|}. A Conjetura das Árvores Graciosas, proposta em 1967, afirma que toda árvore possui uma rotulação graciosa. Um problema relacionado à Conjetura das Árvores Graciosas consiste em determinar se, para todo vértice v de uma árvore T, existe uma rotulação graciosa de T que atribui o rótulo 0 a v. Árvores com tal propriedade são denominadas 0-rotativas. Nesta tese, apresentamos famílias infinitas de caterpillars 0-rotativos. Nossos resultados reforçam a conjetura de que todo caterpillar com diâmetro pelo menos cinco é 0-rotativo.

Também investigamos uma rotulação graciosa mais restrita, chamada rotulação-alpha. Uma rotulação graciosa f de G é uma rotulação-alpha se existir um inteiro k, 0 <= k <= |E(G)|, tal que, para toda aresta uv em E(G), f(u) <= k < f(v) ou f(v) <= k < f(u). Nesta tese, apresentamos duas famílias de lobsters com grau máximo três que possuem rotulações-alpha. Nossos resultados contribuem para uma caracterização de todos os lobsters com grau máximo três que possuem rotulações-alpha.

Na segunda parte desta tese, investigamos generalizações da Conjetura 1,2,3 e da Conjetura 1,2. Dado um grafo simples G = (V(G),E(G)) e um subconjunto L dos números reais, dizemos que uma função f de E(G) em L é uma L-rotulação de arestas de G e dizemos que uma função f da união de V(G) com E(G) em L é uma L-rotulação total de G. Para todo vértice v de G, a cor de v, C(v), é definida como a soma dos rótulos das arestas incidentes em v, se f for uma L-rotulação de arestas de G. Se f for uma L-rotulação total, C(v) é a soma dos rótulos das arestas incidentes no vértice v mais o valor f(v). O par (f,C) é uma L-rotulação de arestas semiforte (L-rotulação total semiforte) se f for uma rotulação de arestas (rotulação total) e C(u) for diferente de C(v) para quaisquer dois vértices adjacentes u,v de G. A Conjetura 1,2,3, proposta em 2004, afirma que todo grafo simples e conexo com pelo menos três vértices possui uma {1,2,3}-rotulação de arestas semiforte. A Conjetura 1,2, proposta em 2010, afirma que todo grafo simples possui uma {1,2}-rotulação total semiforte.

Sejam a,b,c três reais distintos. Nesta tese, nós investigamos {a,b,c}-rotulações de arestas semiforte e {a,b}-rotulações totais semiforte para cinco famílias de grafos: as potências de caminho, as potências de ciclo, os grafos split, os grafos cobipartidos regulares e os grafos multipartidos completos. Provamos que essas famílias possuem tais rotulações para alguns valores reais a,b,c. Como corolário de nossos resultados, obtemos que a Conjetura 1,2,3 e a Conjetura 1,2 são verdadeiras para essas famílias. Além disso, também mostramos que nossos resultados em rotulações de arestas semiforte implicam resultados similares para outro problema de rotulação de arestas relacionado.