Sobre a conjectura de Gallai: problemas associados à decomposição e cobertura de grafos

• Ano de defesa: 2018
• Autor(a) principal: Marco Antonio Ticse Aucahuasi
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; Programa de Pós-Graduação em Matemática; UFMG
• Palavras-chave em Português: Conjectura de Gallai; Decomposição; Cobertura; Matemática - Teses; Método de decomposição
• Link de acesso: http://hdl.handle.net/1843/33515

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.