NP-completeness of graph decomposition problems (Q1179032)

For a fixed graph \(H\), the \(H\)-decomposition problem is as follows: Can a given (input) graph \(G\) be decomposed as an edge disjoint union of subgraphs, all of which are isomorphic to \(H\)? \textit{I. Holyer} [SIAM J. Comput. 10, 797-808 (1981; Zbl 0468.68069)] conjectured that the \(H\)-decomposition problem is \(NP\)-complete whenever \(H\) has at least 3 edges and is connected. Holyer's conjecture had been proved for \(H=K_ m\) (a complete graph), \(P_ m\) (a path) and \(C_ m\) (a cycle). The main result of this paper is: If \(H\) is a connected graph with at least three edges and \(H\) has a vertex \(v\) such that all the vertices adjacent to \(v\), except at most one of them, are of degree one in \(H\), then the \(H\)-decomposition problem is \(NP\)-complete. From this it follows that Holyer's conjecture is true for a family of graphs which includes all trees with at least three edges.