Packing tree factors in random and pseudo-random graphs

zbMATH Open1300.05242arXiv1304.2429MaRDI QIDQ405193FDOQ405193

Authors: Deepak Bal, Michael Krivelevich, Po-Shen Loh, Alan Frieze 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and epsilon > 0, the random graph G_{n,p}, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an epsilon-fraction of its edges, as long as epsilon^4 n p >> (log n)^2. Assuming stronger divisibility conditions, the edge probability can be taken down to p > (C log n)/n. A similar packing result is proved also for pseudo-random graphs, defined in terms of their degrees and co-degrees.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Packing trees of unbounded degrees in random graphs
• Arboricity and spanning‐tree packing in random graphs
• Packing arborescences in random digraphs
• Packing arborescences in random digraphs
• Random packings of graphs
• Packing random graphs and hypergraphs
• scientific article; zbMATH DE number 1300357
• Packing and decomposition of graphs with trees
• An approximate version of the tree packing conjecture via random embeddings
• scientific article; zbMATH DE number 5665909

zbMATH Keywords

packingrandom graphspseudo-random graphstree factors

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Packing Hamilton cycles in random and pseudo-random hypergraphs
• On the existence of a factor of degree one of a connected random graph
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Hamilton decompositions of regular expanders: applications
• Packing tight Hamilton cycles in uniform hypergraphs
• Approximate Hamilton decompositions of random graphs
• Edge-disjoint Hamilton cycles in random graphs
• On factors in random graphs
• Title not available (Why is that?)
• Tree-Matchings in Graph Processes
• Title not available (Why is that?)
• Optimal packings of Hamilton cycles in sparse random graphs
• On two Hamilton cycle problems in random graphs

Cited In (5)

• Packing trees of unbounded degrees in random graphs
• Packing spanning graphs from separable families
• An approximate version of the tree packing conjecture
• Optimal packings of bounded degree trees
• Arboricity and spanning‐tree packing in random graphs

This page was built for publication: Packing tree factors in random and pseudo-random graphs

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