Randomly Pk-decomposable graphs

A graph $G$ is $H$-decomposable if it can be expressed as an edge-disjoint union of subgraphs, each subgraph isomorphic to $H$. If $G$ has the additional property that every $H$-decomposable subgraph of $G$ is part of an $H$-decomposition of $G$, then $G$ is randomly $H$-decomposable. Using computer assistance, we provide in this paper a characterization of randomly path-decomposable graphs for paths of length 11 or less. We also prove the following two results: (1) With one small exception, randomly $P_k$-decomposable graphs with a vertex of odd degree do not contain a $P_{k+1}$-subgraph, (2) When the edges of a $P_k$-subgraph are deleted from a connected randomly $P_k$-decomposable graph, the resulting graph has at most one nontrivial component.