Completing partial packings of bipartite graphs

DOI10.1016/J.JCTA.2011.06.009MaRDI QIDQ640856zbMATH OpenOpenAlexFDO

Authors Ago-Erik Riet, Mykhaylo Tyomkyn, Zoltán Füredi

Publication date 21 October 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.4287

zbMATH Keywords

designsgraph embeddingsgraph packings

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 $nightarrowinfty$. In particular, we prove the conjecture of F"uredi and Lehel cite{FuLe} that $f(n;H)=o(n)$. This settles a long-standing open problem.

Recommendations

• Packing of partial designs
• Packing graphs: The packing problem solved
• scientific article; zbMATH DE number 4148138
• The decomposition threshold for bipartite graphs with minimum degree one
• Integer and fractional packings in dense graphs

Cites work

• A partial \(2k\)-cycle system of order \(n\) can be embedded in a \(2k\)-cycle system of order \(kn+c(k),k\geqslant 3\), where \(c(k)\) is a quadratic function of \(k\)
• A partial kite system of order \(n\) can be embedded in a kite system of order \(8n+9\).
• Embedding partial \(G\)-designs where \(G\) is a 4-cycle with a pendant edge
• scientific article; zbMATH DE number 4150219 (Why is no real title available?)
• scientific article; zbMATH DE number 5778186 (Why is no real title available?)
• scientific article; zbMATH DE number 4081593 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 124520 (Why is no real title available?)
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• scientific article; zbMATH DE number 1289753 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1890841 (Why is no real title available?)
• scientific article; zbMATH DE number 2105042 (Why is no real title available?)
• Regular subgraphs of dense graphs
• Tight embeddings of partial quadrilateral packings

Cited in

(3)

• scientific article; zbMATH DE number 1156587 (Why is no real title available?)
• Packings and Coverings of the Complete Bipartite Graph by Octagons
• On deficiency problems for graphs

This page was built for publication: Completing partial packings of bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640856)