Abstract
Let Bn(X,Y)denote the complete bipartite graph of order n with vertex partition sets X and Y.We prove that for each tree T of order n,there is a packing of k copies of T into a complete bipartite graph Bn+m(X,Y).The ideal of the work comes from the"Tree packing conjecture"made by Gyráfás and Lehel.Bollobás confirmed the"Tree packing conjecture"for many small trees,who showed that one can pack T1,T2,…,Tn/√2 into Kn and that a better bound would follow from a famous conjecture of Erdös.In a similar direction,Hobbs,Bour-geois and Kasiraj made the following conjecture:Any sequence of trees T2,…,Tn,with Ti having order i,can be packed into Kn-1,[n/2].Fur-ther Hobbs,Bourgeois and Kasiraj proved that any two trees can be packed into a complete bipartite graph Kn-1,[n/2].Motivated by these re-sults,Wang Hong proposed the conjecture:For each tree T of order n,there is a k-packing of T in some complete bipartite graph Bn+k-1(X,Y).In this paper,we prove a weak version of this conjecture.
基金项目
National Natural Science Foundation of China(12071334)
NETL
NSTL
维普
万方数据