Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/29009
Title in Portuguese: Número de Turán para cópias disjuntas de caminhos
Title: Turán number for disjoint copies of paths
Author: Lopes, Raul Wayne Teixeira
Advisor(s): Campos, Victor Almeida
Keywords: Teoria extremal dos grafos
Número de Turán
Issue Date: 2017
Citation: LOPES, Raul Wayne Teixeira. Número de Turán para cópias disjuntas de caminhos. 2017. 47 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2017.
Abstract in Portuguese: 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. Nos últimos anos, houve progresso no problema de determinar ex(n, P), onde P é o grafo formado pela união disjunta de k caminhos. Para n suficientemente grande, o problema é bem resolvido. Pouco se sabe, no entanto, sobre o problema para n pequeno. Seja P3 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 = P3. Oferecemos nesta dissertação uma prova construtiva para esta conjectura de Gorgol, determinando assim o valor de ex(n, kP3) para todos n e k. Oferecemos um algoritmo que encontra k cópias disjuntas de P3 em um grafo G = (V, E) suficientemente denso. Mostramos também como podemos encontrar estas k cópias de P3 em tempo O(k|E|).
Abstract: The Turán number ex(n, F) is the maximum number of edges in a graph on n vertices which does not contains F as a subgraph. It is easy to determine ex(n, kF) for small graphs. However, the problem quickly grows in difficulty as we want to avoid bigger graphs or kF, the graph formed by the disjoint union of k copies of F. In the last few years, there was progress in the problem of finding ex(n, P), where P is the graph formed by the disjoint union of k paths. ex(n, P) is well known for sufficiently large n, but little is known of the problem for small n. Let P3 be a path on 3 vertices. Gorgol offered a lower bound for ex(n, kF) when F is a connected graph and, in the same paper, conjectured that this bound is tight when F = P3. In this dissertation, we offer a constructive proof for this conjecture from Gorgol, thus determining ex(n, kP3) for all n and k. We give an algorithm that finds k disjoint copies of P3 in a sufficiently dense graph G = (V, E). We also show how to find those k copies of P3 in time O(k|E|).
URI: http://www.repositorio.ufc.br/handle/riufc/29009
metadata.dc.type: Dissertação
Appears in Collections:DCOMP - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2017_dis_rwtlopes.pdf489,17 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.