Name
Abstract | ||
|---|---|---|
Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let @f"H(n) be the smallest number @f such that any graph G of order n admits an H-decomposition with at most @f parts. Here we determine the asymptotic of @f"H(n) for any fixed graph H as n tends to infinity. The exact computation of @f"H(n) for an arbitrary H is still an open problem. Bollobas [B. Bollobas, On complete subgraphs of different orders, Math. Proc. Cambridge Philos. Soc. 79 (1976) 19-24] accomplished this task for cliques. When H is bipartite, we determine @f"H(n) with a constant additive error and provide an algorithm returning the exact value with running time polynomial in logn. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jctb.2007.03.002 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
order n,fixed graph h,arbitrary h,graph packing,graph decomposition,minimum h-decompositions,exact computation,graphs g,single edge,b. bollobas,graph g,turan graph,regularity lemma,exact value,graph isomorphic,graph isomorphism | Discrete mathematics,Combinatorics,Edge-transitive graph,Graph power,Graph bandwidth,Factor-critical graph,Graph minor,Universal graph,Mathematics,Voltage graph,Complement graph | Journal |
Volume | Issue | ISSN |
97 | 6 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
6 | 0.88 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg Pikhurko | 1 | 318 | 47.03 |
| Teresa Sousa | 2 | 9 | 2.72 |