Article ID Journal Published Year Pages File Type
4646578 Discrete Mathematics 2017 12 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,