Completing partial packings of bipartite graphs
Copyright policy )Completing partial packings of bipartite graphs
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 \rightarrow \infty$. In particular, we prove the conjecture of F��redi and Lehel \cite{FuLe} that $f(n;H) = o(n)$. This settles a long-standing open problem.
- University of Memphis United States
- University of Cambridge United Kingdom
- International Centre for Mathematical Sciences United Kingdom
- University of Illinois at Urbana–Champaign United States
- University of Cambridge
graph embeddings, graph packings, designs, Graph embeddings, Theoretical Computer Science, Graph packings, Computational Theory and Mathematics, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Designs, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO)
graph embeddings, graph packings, designs, Graph embeddings, Theoretical Computer Science, Graph packings, Computational Theory and Mathematics, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Designs, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!