Minimum Weight H-Decompositions of Graphs: The Bipartite Case

Given graphs G and H and a positive number b, a weighted (H,b)-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms an H-subgraph. We assign a weight of b to each H-subgraph in the decomposition and a weight of 1 to single edges. The total weight of the decomposition is the sum of the weights of all elements in the decomposition. Let phi(n, H, b) be the the smallest number such that any graph G of order n admits an (H, b)-decomposition with weight at most phi(n, H, b). The value of the function phi(n, H, b) when b = 1 was determined, for large n, by Pikhurko and Sousa [Minimum H-Decompositions of Graphs, Journal of Combinatorial Theory, B, 97 (2007), 1041-1055.] Here we determine the a symptotic value of phi(n, H, b) for any fixed bipartite graph H and any value of b as n tends to infinity.