On Path Decompositions of Graphs and Multigraphs

Abstract

For graphs G and H, graph G is said to admit an H-decomposition if the edges of G can be partitioned into isomorphic copies of H. Let P4 denote the path on 4 vertices. We survey results that assert that certain graphs and multigraphs admit a P4 decomposition. We then prove that unless P = NP some of these results are best possible by proving that their extensions are NP-complete. The positive results and the NP-complete results provide evidence for a conjecture about P4 decomposability of even-regular multigraphs.