Minimal H-factors and covers
Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G. If G is the complete graph Kn equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for e.g. H=K2. We show that if H contains a cycle, then the minimu