Decomposition of (2K+1)-Regular Graphs Containing Special Spanning 2K-Regular Cayley Graphs Into Paths of Length 2K+1

Uma P_l-decomposição de um grafo G é um conjunto de caminhos aresta-disjuntas com l arestas em G que cobre o conjunto de arestas de G. Favaron, Genest, e Kouider (2010) conjecturaram que todo grafo (2k+1)-regular que contém um emparelhamento perfeito admite uma P_{2k+1}-decomposição. Eles também verificaram essa conjectura para grafos 5-regulares sem ciclos de comprimento 4. Em 2015, Botler, Mota, e Wakabayashi estenderam esse resultado para grafos 5-regulares sem triângulos, e em 2017, Botler, Mota, Oshiro e Wakabayashi generalizaram esse resultado para grafos (2k+1)-regulares com cintura de tamanho pelo menos 2k. Nessa dissertação, verificamos essa conjectura para grafos (2k+1)-regulares que contêm a k-ésima potência de ciclo; e para grafos 5-regulares que contêm um grafo de Cayley gerador 4-regular gerado por dois elementos comutativos.