|
|||||
|
|
Completing partial packings of bipartite graphs |
|
| Authors: | Zoltá n Fü redi,Ago-Erik RietMykhaylo Tyomkyn |
| Affiliation: | a Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA b Rényi Institute of the Hungarian Academy of Sciences, Budapest, P.O. Box 127, H-1364, Hungary c Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152-3240, USA d Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK |
| Abstract: | Given a bipartite graph H and an integer n, let f(n;H) be the smallest integer such that any set of edge disjoint copies of H on n vertices can be extended to an H-design on at most n+f(n;H) vertices. We establish tight bounds for the growth of f(n;H) as n→∞. In particular, we prove the conjecture of Füredi and Lehel (2010) [4] that f(n;H)=o(n). This settles a long-standing open problem. |
| Keywords: | Graph packings Graph embeddings Designs |
| 本文献已被 ScienceDirect 等数据库收录！ | |