Autores

6825
3049,3048
6826
3049,3048

Informações:

Publicações do PESC

Título
Decomposition of (2K+1)-Regular Graphs Containing Special Spanning 2K-Regular Cayley Graphs Into Paths of Length 2K+1
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
17/2/2020
Resumo

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.

Abstract

A P_l-decomposition of a graph G is a set of edge-disjoint paths with l edges in G that cover the edge set of G. Favaron, Genest, and Kouider (2010) conjectured that every simple (2k+1)-regular graph that contains a perfect matching admits a P_{2k+1}-decomposition. They also verified this conjecture for 5-regular graphs without cycles of length 4. In 2015, Botler, Mota, and Wakabayashi extended this result to 5-regular graphs without triangles, and in 2017, Botler, Mota, Oshiro and Wakabayashi generalized this result to (2k+1)-regular graphs with girth at least 2k. In this dissertation, we verify this conjecture for (2k+1)-regular graphs that contain the k-th power of the cycle; and for 5-regular graphs that contain spanning 4-regular Cayley graph generated by two commutative elements.

Arquivo
Topo