Opuscula Math. 24, no. 1 (2004), 97-102
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.
Mathematics Subject Classification: 05C38, 05C85.
- Received: 2004-03-31.