Minimum weight \(H\)-decompositions of graphs: the bipartite case
The electronic journal of combinatorics, Tome 18 (2011) no. 1
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 asymptotic value of $\phi(n,H,b)$ for any fixed bipartite graph $H$ and any value of $b$ as $n$ tends to infinity.
@article{10_37236_613,
author = {Teresa Sousa},
title = {Minimum weight {\(H\)-decompositions} of graphs: the bipartite case},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/613},
zbl = {1330.05134},
url = {http://geodesic.mathdoc.fr/articles/10.37236/613/}
}
Teresa Sousa. Minimum weight \(H\)-decompositions of graphs: the bipartite case. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/613
Cité par Sources :