Open Access
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

© Wuhan University 2023

Licence Creative CommonsThis 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 p-tuple 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 k-parking of G. {L-End} 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 n-vertex 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 k-packing 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 3-packing 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 k-packing 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 k-packing of T in the complete bipartite graph .

The proof is completed.

References

  1. Woźniak M. Packing of graphs—A survey [J]. Discrete Mathematics, 2004, 276: 379-391. [CrossRef] [MathSciNet] [Google Scholar]
  2. Yap H P. Packing of graphs—A survey [J]. Discrete Mathematics, 1988, 38: 395-404. [CrossRef] [MathSciNet] [Google Scholar]
  3. Gyárfás A , Lehel J. Packing trees of different order into Formula [J]. Combinatorics (Proc Fifth Hungarian Colloquia, Keszthely, 1976), Colloquia Mathematica Societatis Ja˙nos Bolyai, 1978, 18: 463-469. [Google Scholar]
  4. Bollobás B. Some remarks on packing trees [J]. Discrete Mathematics, 1983, 46(2): 203-204. [CrossRef] [MathSciNet] [Google Scholar]
  5. Hobbs A M, Bourgeois B A, Kasiraj J. Packing trees in complete graphs [J]. Discrete Mathematics, 1987, 67(1): 27-42. [CrossRef] [MathSciNet] [Google Scholar]
  6. Yuster R. On packing trees into complete bipartite graphs [J]. Discrete Mathematics, 1997, 163(1-3): 325-327. [CrossRef] [MathSciNet] [Google Scholar]
  7. Wang H. Packing three copies of a tree into a complete bipartite graph [J]. Annals of Combinatorics, 2009, 13(2): 261-269. [CrossRef] [MathSciNet] [Google Scholar]
  8. Wang H. Packing two forests into a bipartite graph [J]. Journal of Graph Theory, 1996, 23(2): 209-213. [CrossRef] [MathSciNet] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text 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 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.