Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1 - Botler, Fábio; Hoffmann, Luiz (Anais do Encontro de Teoria da Computação (ETC); 2020: Anais do V Encontro de Teoria da Computação, 2020)
A P l -decomposition of a graph G is a set of paths with l edges in G that cover the edge set of G. Favaron, Genest, and Kouider (2010) conjectured that every (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. In this paper, we verify this conjecture for (2k+1)-regular graphs that contain the k-th power of a spanning cycle; and for 5-regular graphs that contain certain spanning 4-regular Cayley graphs.