On the decomposition of graphs into copies of $P_3\cup t{K}_2$

Abstract

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 t{K}_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.