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

• Fábio Botler UFRJ http://orcid.org/0000-0003-2028-199X
• Luiz Hoffmann UFRJ

DOI: https://doi.org/10.5753/etc.2020.11078

Resumo

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.

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

Referências

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.