Número de Turán para cópias disjuntas de caminhos

Detalhes bibliográficos
Ano de defesa: 2017
Autor(a) principal: Lopes, Raul Wayne Teixeira
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/29009
Resumo: 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|).