1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Decomposing 10-Regular Graphs into Paths of Length 5

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1089 - 1097
Received: 29 Oct 2019
Accepted: 04 May 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

[1] 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 Search in Google Scholar

[2] 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 Search in Google Scholar

[3] 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 Search in Google Scholar

[4] J. Erde, Decomposing the cube into paths, Discrete Math. 336 (2014) 41–45. https://doi.org/10.1016/j.disc.2014.07.019 Search in Google Scholar

[5] 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 Search in Google Scholar

[6] 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.10.1017/CBO9781107359949.007 Search in Google Scholar

[7] 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 Search in Google Scholar

[8] 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 Search in Google Scholar

[9] M. Kouider and Z. Lonc, Path decompositions and perfect path double covers, Australas. J. Combin. 19 (1999) 261–274. Search in Google Scholar

[10] J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 193–220. https://doi.org/10.1007/BF02392606 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo