Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646578 | Discrete Mathematics | 2017 | 12 Pages |
Abstract
A conjecture by Bollobás from 1995 (which is a weakening of the famous Tree Packing Conjecture by Gyárfás from 1976) states that any set of kk trees Tn,Tn−1,…,Tn−k+1Tn,Tn−1,…,Tn−k+1, such that Tn−iTn−i has n−in−i vertices, pack into KnKn, provided nn is sufficiently large. We confirm Bollobás conjecture for trees Tn,Tn−1,…,Tn−k+1Tn,Tn−1,…,Tn−k+1, such that Tn−iTn−i has k−1−ik−1−i leaves or a pending path of order k−1−ik−1−i. As a consequence we obtain that the conjecture is true for k≤5k≤5.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Andrzej Żak,