Mathematics

CLC number: O157.5

On Packing Trees into Complete Bipartite Graphs

¹ Department of Mathematics, Suzhou University of Science and Technology, Suzhou 215009, Jiangsu, China
² Department of Mathematics, University of Idaho, Moscow 83844-1103, Idaho, US

Received: 7 May 2022

Abstract

Let $B_n(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 $B_{n+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 $T_{\mathrm{1}},T_{\mathrm{2}},\cdots ,T_{n/\sqrt[]{\mathrm{2}}}$ into $K_n$ and that a better bound would follow from a famous conjecture of Erd$\ddot{\mathrm{o}}$s. In a similar direction, Hobbs, Bourgeois and Kasiraj made the following conjecture: Any sequence of trees $T_{\mathrm{2}}$, … , $T_n$, with $T_i$ having order $i$, can be packed into $K_{n-\mathrm{1},\lceil n/\mathrm{2}\rceil }$. Further Hobbs, Bourgeois and Kasiraj proved that any two trees can be packed into a complete bipartite graph $K_{n-\mathrm{1},\lceil n/\mathrm{2}\rceil }$. Motivated by these results, Wang Hong proposed the conjecture: For each tree $T$ of order $n$, there is a $k$⁃packing of $T$ in some complete bipartite graph $B_{n+k-\mathrm{1}}(X,Y)$. In this paper, we prove a weak version of this conjecture.