Título: Número de Turán para Cópias Disjuntas de Caminhos.

Data: 20/02/2017 Horário: 16h Local: Sala de Seminários - Bloco 952 - Campus do Pici

Resumo:

O número de Turán ex(n, F) é o número máximo de arestas que um grafo em n vértices pode ter sem conter F como subgrafo. Determinar ex(n, kF) para alguns grafos pequenos é fácil. Porém, o problema cresce rapidamente de dificuldade quando consideramos grafos maiores ou quando queremos determinar ex(n, kF), onde kF é o grafo formado por k cópias disjuntas do grafo F. Seja H o grafo formado pela união disjunta de k caminhos. Nos últimos anos, houve progresso no problema de determinar ex(n, H). Para n suficientemente grande, o problema é bem resolvido. Pouco se sabe, no entanto, sobre o problema para n pequeno. Seja P_3 o grafo formado por um caminho em 3 vértices. Gorgol ofereceu um limite inferior para ex(n, kF) quando F é um grafo conexo e, no mesmo artigo, conjecturou que este limite é apertado quando F = P_3. Oferecemos nesta dissertação uma prova construtiva para esta conjectura de Gorgol, determinando assim o valor de ex(n, kP_3) para todos n e k. Oferecemos um algoritmo que encontra k cópias disjuntas de P_3 em um grafo G = (V,E) suficientemente denso. Mostramos também como podemos encontrar estas k cópias de P_3 em tempo O(k|E|).

Banca:

• Prof. Dr. Victor Almeida Campos (MDCC/UFC - Orientador)
• Prof. Dr. Fabrício Siqueira Benevides (MAT/UFC)
• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC)