Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1


A Pl-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 P2k+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.

Palavras-chave: Decomposition, regular graph, Cayley graph, path


Botler, F., Mota, G. O., Oshiro, M. T. I., and Wakabayashi, Y. (2017). Decomposing regular graphs with prescribed girth into paths of given length. Eur J Combin, 66:28–36.

Botler, F., Mota, G. O., and Wakabayashi, Y. (2015). Decompositions of triangle-free 5-regular graphs into paths of length five. Discrete Mathematics, 338(11):1845–1855.

Bouchet, A. and Fouquet, J.-L. (1983). Trois types de decompositions d’un graphe en chaînes. In North-Holland Mathematics Studies, volume 75, pages 131–141. Elsevier.

Favaron, O., Genest, F., and Kouider, M. (2010). Regular path decompositions of odd regular graphs. Journal of Graph Theory, 63(2):114–128.

Godsil, C. and Royle, G. F. (2013). Algebraic graph theory, volume 207. Springer Science & Business Media.

Gross, J. L. (1977). Every connected regular graph of even degree is a Schreier coset graph. Journal of Combinatorial Theory, Series B, 22(3):227–232.

Kotzig, A. (1957). Aus der Theorie der endlichen regularen Graphen dritten und vierten Grades. Casopis Pest. Mat, 82:76–92.
Como Citar

Selecione um Formato
BOTLER, Fábio; HOFFMANN, Luiz. Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 13-16. ISSN 2595-6116. DOI: