An \(H\)-decomposition of a graph \(G\) is a representation of \(G\) as an edge disjoint union of subgraphs, all of which are isomorphic to another graph \(H\). We study the case where \(H\) is \(P_3 \cup tK_2\) – the vertex disjoint union of a simple path of length 2 (edges) and \(t\) isolated edges – and prove that a set of three obviously necessary conditions for \(G = (V, E)\) to admit an \(H\)-decomposition, is also sufficient if \(|E|\) exceeds a certain function of \(t\). A polynomial time algorithm to test \(H\)-decomposability of an input graph \(G\) immediately follows.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.