Randomly Pk-decomposable graphs

AbstractA 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 Pk-decomposable graphs with a vertex of odd degree do not contain a Pk+1-subgraph, (2) When the edges of a Pk-subgraph are deleted from a connected randomly Pk-decomposable graph, the resulting graph has at most one nontrivial component