Bull. Korean Math. Soc. 2022; 59(2): 345-350
Online first article March 31, 2022 Printed March 31, 2022
https://doi.org/10.4134/BKMS.b210147
Copyright © The Korean Mathematical Society.
Suzhou University of Science and Technology; University of Idaho
In this work, we confirm a weak version of a conjecture proposed by Hong Wang. The ideal of the work comes from the tree packing conjecture made by Gy\'arf\'as and Lehel. Bollob\'as confirms the tree packing conjecture for many small tree, who showed that one can pack $T_1,T_2,\ldots,T_{n/\sqrt{2}}$ into $K_n$ and that a better bound would follow from a famous conjecture of Erd\H{o}s. In a similar direction, Hobbs, Bourgeois and Kasiraj made the following conjecture: Any sequence of trees $T_1,T_2,\ldots,T_n$, with $T_i$ having order $i$, can be packed into $K_{n-1,\lceil n/2\rceil}$. Further Hobbs, Bourgeois and Kasiraj [3] proved that any two trees can be packed into a complete bipartite graph $K_{n-1,\lceil n/2\rceil}$. Motivated by the result, Hong Wang propose the conjecture: For each $k$-partite tree $T(\mathbb{X})$ of order $n$, there is a restrained packing of two copies of $T(\mathbb{X})$ into a complete $k$-partite graph $B_{n+m}(\mathbb{Y})$, where $m=\lfloor\frac{k}{2}\rfloor$. Hong Wong \cite{4} confirmed this conjecture for $k=2$. In this paper, we prove a weak version of this conjecture.
Keywords: Packing of graphs, tree packing conjecture, $k$-partite tree
MSC numbers: 05C70
Supported by: This work was supported by the National NSF of China (no. 12071334, 11871270).
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd