Asymptotically optimal tree-packings in regular graphs

MaRDI QIDQ5950387zbMATH OpenFDO

Authors Alexander Kelmans, Dhruv Mubayi, Benny Sudakov

Publication date 11 December 2001

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

Full work available at URL https://eudml.org/doc/122004, http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r38.html

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

zbMATH Keywords

matchings in hypergraphstree-packings

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Review text

Let \(T\) be a tree with \(t\) vertices. If \(G\) is a graph, then a \(T\)-packing of \(G\) is a subgraph of \(G\) each of whose connected components is isomorphic to \(T\). Clearly, if \(G\) has \(n\) vertices, then a \(T\)-packing of \(G\) contains at most \(n/t\) connected components. The authors prove the following asymptotic result for the maximum number of components in a \(T\)-packing. For every \(\varepsilon> 0\) there exists a real number \(D(\varepsilon, t)>0\) such that, if \(d> D(\varepsilon, t)\) and \(G\) is a simple \(d\)-regular graph on \(n\) vertices, then \(G\) contains at least \((1-\varepsilon)n/t\) vertex disjoint trees isomorphic to \(T\).

Recommendations

• On the tree packing conjecture
• Packing trees of unbounded degrees in random graphs
• Packing Trees into the Complete Graph
• Packing trees in complete graphs
• Packing and decomposition of graphs with trees

Cited in

(9)

• Hamiltonicity and pancyclicity of Cartesian products of graphs
• Problems and results in extremal combinatorics. I.
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Hamiltonicity and pancyclicity of generalized prisms
• Tree decompositions of graphs without large bipartite holes
• Packing 3-vertex paths in claw-free graphs and related topics
• Nearly Hamilton cycles in sublinear expanders and applications
• Edge-disjoint cycles with the same vertex set
• Packing subdivisions into regular graphs

This page was built for publication: Asymptotically optimal tree-packings in regular graphs

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