On decomposing even regular multigraphs into small isomorphic trees

摘要

It is known that P_4, the path with 3 edges, decomposes every 6-regular simple graph. It is also known that P_4 decomposes the multigraph obtained by doubling each edge of a cubic graph. We show that P_4 decomposes every 6-regular multigraph with edge multiplicity at most 2. This in turn implies that P_4 decomposes every 6k-regular multigraph with edge multiplicity at most 2k. We also investigate decompositions of certain 2n-regular multigraphs with edge multiplicity at most 2 into double-stars with n edges.