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|). |
