Article ID Journal Published Year Pages File Type
4647203 Discrete Mathematics 2014 5 Pages PDF
Abstract
It is known that P4, the path with 3 edges, decomposes every 6-regular simple graph. It is also known that P4 decomposes the multigraph obtained by doubling each edge of a cubic graph. We show that P4 decomposes every 6-regular multigraph with edge multiplicity at most 2. This in turn implies that P4 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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,