Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/33515| Tipo: | Dissertação |
| Título: | Sobre a conjectura de Gallai: problemas associados à decomposição e cobertura de grafos |
| Autor(es): | Marco Antonio Ticse Aucahuasi |
| Primeiro Orientador: | Bhalchandra Digambar Thatte |
| Resumo: | Este trabalho está baseado no estudo da conjectura de Gallai (1966), que nos diz que qualquer grafo conexo com n vértices pode ser decomposto em no máximo bn+1 2 c caminhos aresta-disjuntos. Apresenta-se um dos primeiros resultados obtidos por Lovász (1968),que afirma que se um grafo tem no máximo um vértice de grau par, então a conjectura é verdadeira. Brevemente, estuda-se as decomposições por árvores e grafos completos. Estudamos os trabalhos de Donald(1980) e Pyber(1996) que estenderam a técnica de Lovász. Finalmente,estudamos o resultado de Fan(2005)que afirma que se um sub grafo induzido por vértices de grau par de um grafo G é um grafo com certa propriedade, então a conjectura é verdadeira para G. |
| Abstract: | This work is based on the study of Gallai’s conjecture (1966), which tells us that any connected graph with n vertices can be decomposed into at most bn+1 2 c edge-disjoint paths. One of the first results by Lovász (1968) is presented. It asserts that if a graph has at most one vertex of even degree, then the conjecture is true. Decompositions by trees and complete graphs are studied. We also study works of Donald(1980) and Pyber(1996) which extend Lovász’s technique. Finally we study the result of Fan (2005) which states that if subgraph induced by even-degree vertices of a graph G is a graph with a certain property, then the conjecture is true for G. |
| Assunto: | Matemática - Teses Conjectura de Gallai Método de decomposição |
| Idioma: | por |
| País: | Brasil |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Instituição: | UFMG |
| Curso: | Programa de Pós-Graduação em Matemática |
| Tipo de Acesso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/33515 |
| Data do documento: | 14-Dez-2018 |
| Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| Diss315.pdf | 887.67 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.