Random packing by ρ-connected ρ-regular graphs Original Research Article

A graph G is packable by the graph F if its edges can be partitioned into copies of F. If deleting the edges of any F-packable subgraph from G leaves an F-packable graph, then G is randomly F-packable. If G is F-packable but not randomly F-packable then G is F-forbidden. The minimal F-forbidden graphs provide a characterization of randomly F-packable graphs. We show that for each ρ-connected ρ-regular graph F with ρ > 1, there is a set R(F) of minimal F-forbidden graphs of a simple form, such that any other minimal F-forbidden graph can be obtained from a graph in R(F) by a process of identifying vertices and removing copies of F. When F is a connected strongly edge-transitive graph having more than one edge (such as a cycle or hypercube), there is only one graph in R(F).