Article in volume
Authors:
Title:
Decomposing 10-regular graphs into paths of length 5
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1089-1097
Received: 2019-10-29 , Revised: 2020-05-02 , Accepted: 2020-05-04 , Available online: 2020-06-03 , https://doi.org/10.7151/dmgt.2334
Abstract:
Let $G$ be a 10-regular graph which does not contain any 4-cycles. In this
paper, we prove that $G$ can be decomposed into paths of length 5, such that
every vertex is a terminal of exactly two paths.
Keywords:
10-regular graph, decomposition, path
References:
- F. Botler, G.O. Mota, M.T.I. Oshiro and Y. Wakabayashi, Decomposing regular graphs with prescribed girth into paths of given length, European J. Combin. 66 (2017) 28–36.
https://doi.org/10.1016/j.ejc.2017.06.011 - F. Botler and A. Talon, Decomposing $8$-regular graphs into paths of length $ 4$, Discrete Math. 340 (2017) 2275–2285.
https://doi.org/10.1016/j.disc.2017.04.024 - S.I. El-Zanati, M. Ermete, J. Hasty, M.J. Plantholt and S. Tipnis, On decomposing regular graphs into isomorphic double-stars, Discuss. Math. Graph Theory 35 (2015) 73–79.
https://doi.org/10.7151/dmgt.1779 - J. Erde, Decomposing the cube into paths, Discrete Math. 336 (2014) 41–45.
https://doi.org/10.1016/j.disc.2014.07.019 - J.F. Fink, On the decomposition of n-cubes into isomorphic trees, J. Graph Theory 14 (1990) 405–411.
https://doi.org/10.1002/jgt.3190140403 - R. Häggkvist, Decompositions of complete bipartite graphs, in: Surveys in Combinatorics, J. Siemons (Ed(s)), (London Math. Soc. Lecture Note Ser. 1989) 115–147.
- M.S. Jacobson, M. Truszczyński and Zs. Tuza, Decompositions of regular bipartite graphs, Discrete Math. 89 (1991) 17–27.
https://doi.org/10.1016/0012-365X(91)90396-J - K.F. Jao, A.V. Kostochka and D.B. West, Decomposition of Cartesian products of regular graphs into isomorphic trees, J. Comb. 4 (2013) 469–490.
https://doi.org/10.4310/JOC.2013.v4.n4.a6 - M. Kouider and Z. Lonc, Path decompositions and perfect path double covers, Australas. J. Combin. 19 (1999) 261–274.
- J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 193–220.
https://doi.org/10.1007/BF02392606
Close