Edge decompositions of multigraphs into multi-2-paths

Abstract

We establish the computational time complexity of the existence problem of a decomposition of an instance multigraph into isomorphic 3-vertex paths with multiple edges. If the two edge multiplicities are distinct, the problem is NPC; if mutually equal then polynomial.

Keywords

• edge decomposition
• multigraph
• multipath
• path
• time complexity