Minimum weight \(H\)-decompositions of graphs: the bipartite case (Q547786)

Summary: 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 \(\varphi (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 \(\varphi (n, H, b)\). The value of the function \(\varphi (n, H, b)\) when \(b = 1\) for large \(n\) was already determined [\textit{O. Pikhurko} and \textit{T. Sousa}, J. Comb. Theory, Ser. B 97, No. 6, 1041--1055 (2007; Zbl 1125.05085)]. Here we determine the asymptotic value of \(\varphi (n, H, b)\) for any fixed bipartite graph \(H\) and any value of \(b\) as \(n\) tends to infinity.