Uma decomposição de um grafo G é um conjunto D = {H_1,... , H_k } de subgrafos de G dois-a-dois aresta-disjuntos que cobre o conjunto das arestas de G. Se H_i é isomorfo a um grafo fixo H, para 1<=i<=k, então dizemos que D é uma H-decomposição de G. Neste trabalho, estudamos o caso em que H é um caminho de comprimento fixo. Para isso, primeiramente decompomos o grafo dado em trilhas, e depois fazemos uso de um lema de desemaranhamento, que nos permite transformar essa decomposição em trilhas numa decomposição somente em caminhos. Com isso, obtemos resultados para três conjecturas sobre H-decomposição de grafos no caso em que H=P_\\ell é o caminho de comprimento \\ell. Dois desses resultados resolvem versões fracas das Conjecturas de Kouider e Lonc (1999) e de Favaron, Genest e Kouider (2010), ambas para grafos regulares. Provamos que, para todo inteiro positivo \\ell, (i) existe um inteiro positivo m_0 tal que se G é um grafo 2m\\ell-regular com m>=m_0, então G admite uma P_\\ell-decomposição; (ii) se \\ell é ímpar, existe um inteiro positivo m_0 tal que se G é um grafo m\\ell-regular com m>=m_0, e G contém um m-fator, então G admite uma P_\\ell-decomposição. O terceiro resultado diz respeito a grafos altamente aresta- conexos: existe um inteiro positivo k_\\ell tal que se G é um grafo k_\\ell-aresta-conexo cujo número de arestas é divisível por \\ell, então G admite uma P_\\ell-decomposição. Esse resultado prova que a Decomposition Conjecture de Barát e Thomassen (2006), formulada para árvores, é verdadeira para caminhos. / A decomposition of a graph G is a set D = {H_1,...,H_k} of pairwise edge-disjoint subgraphs of G that cover the set of edges of G. If H_i is isomorphic to a fixed graph H, for 1<=i<=k, then we say that D is an H-decomposition of G. In this work, we study the case where H is a path of fixed length. For that, we first decompose the given graph into trails, and then we use a disentangling lemma, that allows us to transform this decomposition into one consisting only of paths. With this approach, we tackle three conjectures on H-decomposition of graphs and obtain results for the case H=P_\\ell is the path of length \\ell. Two of these results solve weakenings of a conjecture of Kouider and Lonc (1999) and a conjecture of Favaron, Genest and Kouider (2010), both for regular graphs. We prove that, for every positive integer \\ell, (i) there is a positive integer m_0 such that, if G is a 2m\\ell-regular graph with m>=m_0, then G admits a P_\\ell-decomposition; (ii) if \\ell is odd, there is a positive integer m_0 such that, if G is an m\\ell-regular graph with m>=m_0 containing an m-factor, then G admits a P_\\ell-decomposition. The third result concerns highly edge-connected graphs: there is a positive integer k_\\ell such that if G is a k_\\ell-edge-connected graph whose number of edges is divisible by \\ell, then G admits a P_\\ell-decomposition. This result verifies for paths the Decomposition Conjecture of Barát and Thomassen (2006), on trees.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-06092016-143525 |
| Date | 24 February 2016 |
| Creators | Fábio Happ Botler |
| Contributors | Yoshiko Wakabayashi, Orlando Lee, Daniel Morgato Martin, Cândida Nunes da Silva, Jayme Luiz Szwarcfiter |
| Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds