Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/9599| Tipo: | Dissertação |
| Título : | A conjectura de Tuza sobre triângulos em grafos |
| Título en inglés: | The conjecture of Tuza about triangles in graphs |
| Autor : | Freitas, Lucas Ismaily Bezerra |
| Tutor: | Lee, Orlando |
| Palabras clave : | Teoria dos Grafos;Empacotamento e cobertura combinatória;Conjectura de Tuza |
| Fecha de publicación : | 2014 |
| Citación : | FREITAS, L. I. B. A conjectura de Tuza sobre triângulos em grafos. 2014. 83 f. Dissertação (Mestrado Ciência da Computação) - Instituto de Computação, Universidade Estadual de Campinas, Campinas, 2014. |
| Resumen en portugués brasileño: | Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação¸ nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contraexemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K5. |
| Abstract: | In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza’s conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K5 minor. |
| URI : | http://www.repositorio.ufc.br/handle/riufc/9599 |
| Aparece en las colecciones: | CQUIXADA - Dissertações defendidas em outras instituições |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 2014_dis_libfreitas.pdf | 1,79 MB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.