Issue 
Wuhan Univ. J. Nat. Sci.
Volume 28, Number 3, June 2023



Page(s)  221  222  
DOI  https://doi.org/10.1051/wujns/2023283221  
Published online  13 July 2023 
Mathematics
CLC number: O157.5
On Packing Trees into Complete Bipartite Graphs
^{1}
Department of Mathematics, Suzhou University of Science and Technology, Suzhou 215009, Jiangsu, China
^{2}
Department of Mathematics, University of Idaho, Moscow 838441103, Idaho, US
Received:
7
May
2022
Let denote the complete bipartite graph of order with vertex partition sets and . We prove that for each tree of order , there is a packing of copies of into a complete bipartite graph . 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 into and that a better bound would follow from a famous conjecture of Erds. In a similar direction, Hobbs, Bourgeois and Kasiraj made the following conjecture: Any sequence of trees , … , , with having order , can be packed into . Further Hobbs, Bourgeois and Kasiraj proved that any two trees can be packed into a complete bipartite graph . Motivated by these results, Wang Hong proposed the conjecture: For each tree of order , there is a ⁃packing of in some complete bipartite graph . In this paper, we prove a weak version of this conjecture.
Key words: packing of graphs / tree packing conjecture / embedding of graph
Biography: PENG Yanling, female, Professor, research direction: graph theory. Email: pengyanling@mail.usts.edu.cn
Fundation item: Supported by the National Natural Science Foundation of China (12071334)
© Wuhan University 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
0 Introduction
For graphs G and H, an embedding of G into H is an injection such that whenever . A packing of p graphs into is a ptuple such that, for , is an embedding of into H and the p sets are mutually disjoint. When all are isomorphic to G, we call it a kparking of G. {LEnd} A bipartite graph G with the vertex partition is denoted as or . For a packing of into a bipartite graph , we mean that is a packing such that , ,
Packing problems are central to combinatorics. Many classical problems can be stated as packing problems, such as Mantel's Theorem which can be formulated by saying that if G is an nvertex graph with less than edges, then the two graphs and G can be packed into . The packing problem has received a lot of attention. Many interesting results and elegant proofs of these results were obtained. For a survey, see Refs.[1,2]. Among the best known packing problems, the famous tree packing conjecture of Gyráfás and Lehel has driven a large amount of research in the area.
Conjecture 1 (Gyráfás and Lehel^{ [3]}) Given and trees with having order , the graphs can be packed into complete graph .
A packing of many of the small trees from Conjecture 1 was obtained by Bollobs^{ [4]}, who showed that one can pack into and that a better bound would follow from a famous conjecture of Erds. In a similar direction, Hobbs, Bourgeois and Kasiraj made the following conjecture.
Conjecture 2 (Hobbs, Bourgeois and Kasiraj^{[5]}) Any sequence of trees , with having order i, can be packed into .
The conjecture has been verified for several very special classes of trees. Hobbs, Bourgeois and Kasiraj^{[5] }proved that any two trees of order m and n with can be packed into a complete bipartite graph . Yuster^{[6]} proved that any sequence of trees , can be packed into . Motivated by these results, Wang proposed the following conjecture.
Conjecture 3 (Wang^{ [7]}) For each tree T of order n, there is a kpacking of T in some complete bipartite graph .
This conjecture is true for and (see Theorem 1 and Theorem 2).
Theorem 1^{[8]} Let and be two trees of order with . Then there exists a complete bipartite graph such that there is a packing of and in .
Theorem 2^{[7]} For each tree T of order n, there is a 3packing of T in some complete bipartite graph .
In this paper we prove the following theorem.
Theorem 3 For each tree T of order n, whose bipartite vertex classes are of size and , there is a kpacking of T in some complete bipartite graph , where , and .
1 Proof of Theorem 3
We recall the following lemma due to Yuster^{[6]}.
Lemma 1^{[6]} Let H be a bipartite graph with vertex classes and of sizes and , respectively, . Let T be a tree whose bipartite vertex classes are of size and . If and and then H contains a subgraph isomorphic to T.
Proof of Theorem 3 Let T be a tree of order n, whose bipartite vertex classes are of size and , where . Let be a complete bipartite graph of order n with vertex partition sets X and Y of sizes and , respectively. Now we add some vertices into X and Y such that , , and . So we get a complete bipartite graph of order , where . Clearly, contains a copy of T. Suppose that we have already packed copies of T in . Let H be the spanning subgraph of which contains all the edges that do not appear in the packing. It is easy to see that Since , we have . By Lemma 1, we find a copy of T in H, and add T to the packing. So there is a kpacking of T in the complete bipartite graph .
The proof is completed.
References
 Woźniak M. Packing of graphs—A survey [J]. Discrete Mathematics, 2004, 276: 379391. [CrossRef] [MathSciNet] [Google Scholar]
 Yap H P. Packing of graphs—A survey [J]. Discrete Mathematics, 1988, 38: 395404. [CrossRef] [MathSciNet] [Google Scholar]
 Gyárfás A , Lehel J. Packing trees of different order into [J]. Combinatorics (Proc Fifth Hungarian Colloquia, Keszthely, 1976), Colloquia Mathematica Societatis Ja˙nos Bolyai, 1978, 18: 463469. [Google Scholar]
 Bollobás B. Some remarks on packing trees [J]. Discrete Mathematics, 1983, 46(2): 203204. [CrossRef] [MathSciNet] [Google Scholar]
 Hobbs A M, Bourgeois B A, Kasiraj J. Packing trees in complete graphs [J]. Discrete Mathematics, 1987, 67(1): 2742. [CrossRef] [MathSciNet] [Google Scholar]
 Yuster R. On packing trees into complete bipartite graphs [J]. Discrete Mathematics, 1997, 163(13): 325327. [CrossRef] [MathSciNet] [Google Scholar]
 Wang H. Packing three copies of a tree into a complete bipartite graph [J]. Annals of Combinatorics, 2009, 13(2): 261269. [CrossRef] [MathSciNet] [Google Scholar]
 Wang H. Packing two forests into a bipartite graph [J]. Journal of Graph Theory, 1996, 23(2): 209213. [CrossRef] [MathSciNet] [Google Scholar]
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.