Minimum Weight H-Decompositions of Graphs: The Bipartite Case

Research output: Contribution to journalArticle

Abstract

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.
Original languageUnknown
Pages (from-to)P126
JournalElectronic Journal Of Combinatorics
Volume18
Issue number1
Publication statusPublished - 1 Jan 2011

Cite this