On Packing Trees into Complete Bipartite Graphs

Yanling PENG; Hong WANG

doi:10.1051/wujns/2023283221

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 Journal of Natural Sciences, 2023, Vol.28 No.3, 221-222

Mathematics

CLC number: O157.5

On Packing Trees into Complete Bipartite Graphs

Yanling PENG¹ and Hong WANG²

¹ 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)$ Mathematical equation 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 Gyráfás and Lehel. Bollobás confirmed the "Tree packing conjecture" for many small trees, who showed that one can pack $T_{1}, T_{2}, \dots, T_{n / \sqrt[]{2}}$ Mathematical equation into $K_{n}$ and that a better bound would follow from a famous conjecture of Erd $\ddot{o}$ s. In a similar direction, Hobbs, Bourgeois and Kasiraj made the following conjecture: Any sequence of trees $T_{2}$ , … , $T_{n}$ , with $T_{i}$ having order $i$ , can be packed into $K_{n - 1, ⌈ n / 2 ⌉}$ Mathematical equation . Further Hobbs, Bourgeois and Kasiraj proved that any two trees can be packed into a complete bipartite graph $K_{n - 1, ⌈ n / 2 ⌉}$ . 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 - 1} (X, Y)$ Mathematical equation . 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. E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

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 $ϕ : V (G) \to V (H)$ Mathematical equation such that $ϕ (a) ϕ (b) \in E (H)$ whenever $a b \in E (G)$ . A packing of p graphs $G_{1}, G_{2}, \dots,$ $G_{p}$ into $H$ is a p-tuple $Φ = (ϕ_{1}, ϕ_{2}, \dots, ϕ_{p})$ such that, for $i = 1,2, \dots, p$ , $ϕ_{i}$ is an embedding of $G_{i}$ into H and the p sets $ϕ_{i} (E (G_{i}))$ Mathematical equation are mutually disjoint. When all $G_{i}$ are isomorphic to G, we call it a k-parking of G. {L-End} A bipartite graph G with the vertex partition $X = (X_{1}, X_{2})$ is denoted as $G (X_{1}, X_{2})$ or $G (X)$ . For a packing $Φ = (ϕ_{1}, ϕ_{2}, \dots, ϕ_{p})$ of $G_{1} (X), G_{2} (X), \dots, G_{p} (X)$ Mathematical equation into a bipartite graph $H (Y)$ , we mean that $Φ$ is a packing such that $ϕ_{i} (X_{j}) \subset Y_{j}$ , $i = 1, 2, \dots, p$ , $j = 1,2 .$

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 $(\begin{matrix} n \\ 2 \end{matrix}) - \frac{n^{2}}{4}$ Mathematical equation edges, then the two graphs $K_{3}$ and G can be packed into $K_{n}$ . 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 Gyráfás and Lehel has driven a large amount of research in the area.

Conjecture 1 (Gyráfás and Lehel^[3]) Given $n \in N$ Mathematical equation and trees $T_{1}, \dots, T_{n}$ with $T_{i}$ having order $i$ , the graphs $T_{1}, \dots, T_{n}$ can be packed into complete graph $K_{n}$ .

A packing of many of the small trees from Conjecture 1 was obtained by Bollob $\dot{a}$ Mathematical equation s^[4], who showed that one can pack $T_{1}, \dots, T_{n / \sqrt[]{2}}$ into $K_{n}$ and that a better bound would follow from a famous conjecture of Erd $\ddot{o}$ s. In a similar direction, Hobbs, Bourgeois and Kasiraj made the following conjecture.

Conjecture 2 (Hobbs, Bourgeois and Kasiraj^[5]) Any sequence of trees $T_{2}, \dots, T_{n}$ Mathematical equation , with $T_{i}$ having order i, can be packed into $K_{n - 1, ⌈ n / 2 ⌉}$ .

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 $m < n$ Mathematical equation can be packed into a complete bipartite graph $K_{n - 1, ⌈ n / 2 ⌉}$ . Yuster^[6] proved that any sequence of trees $T_{2}, \dots, T_{s}$ , $s < \sqrt[]{5 / 8} n$ can be packed into $K_{n - 1, ⌈ n / 2 ⌉}$ . 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 $B_{n + k - 1} (X, Y)$ Mathematical equation .

This conjecture is true for $k = 2$ Mathematical equation and $k = 3$ (see Theorem 1 and Theorem 2).

Theorem 1^[8] Let $S (U_{0}, U_{1})$ Mathematical equation and $T (V_{0}, V_{1})$ be two trees of order $n$ with $| U_{i} | = | V_{i} | (i = 0,1)$ . Then there exists a complete bipartite graph $B_{n + 1} (X_{0}, X_{1})$ such that there is a packing of $S (U_{0}, U_{1})$ and $T (V_{0}, V_{1})$ in $B_{n + 1} (X_{0}, X_{1})$ Mathematical equation .

Theorem 2^[7] For each tree T of order n, there is a 3-packing of T in some complete bipartite graph $B_{n + 2} (X, Y)$ Mathematical equation .

In this paper we prove the following theorem.

Theorem 3 For each tree T of order n, whose bipartite vertex classes are of size $k_{1}$ Mathematical equation and $k_{2}$ , there is a k-packing of T in some complete bipartite graph $B_{n + m} (X, Y)$ , where $m = (h_{1} - k_{1}) + (h_{2} - k_{2})$ , $h_{1} = | X |$ and $h_{2} = | Y |$ .

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 $H_{1}$ Mathematical equation and $H_{2}$ of sizes $h_{1}$ and $h_{2}$ , respectively, $h_{1} \leq h_{2}$ . Let T be a tree whose bipartite vertex classes are of size $k_{1}$ and $k_{2}$ . If $k_{1} \leq h_{1}$ and $k_{2} \leq h_{2}$ and $e (H) \geq k_{2} h_{1} + k_{1} h_{2} + k_{1} + k_{2} - h_{1} - h_{2} - k_{1} k_{2},$ Mathematical equation 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 $k_{1}$ Mathematical equation and $k_{2}$ , where $k_{1} + k_{2} = n$ . Let $B_{n} (X, Y)$ be a complete bipartite graph of order n with vertex partition sets X and Y of sizes $k_{1}$ and $k_{2}$ , respectively. Now we add some vertices into X and Y such that $| X | = h_{1}$ , $| Y | = h_{2}$ , $h_{1} \leq h_{2}$ Mathematical equation and $(h_{1} - k_{1}) (h_{2} - k_{2}) + (h_{1} - k_{1}) + (h_{2} - k_{2}) \geq (k - 1) (n - 1)$ . So we get a complete bipartite graph $B_{n + m} (X, Y)$ of order $n + m$ , where $m = (h_{1} - k_{1}) + (h_{2} - k_{2})$ . Clearly, $B_{n + m} (X, Y)$ contains a copy of T. Suppose that we have already packed $k - 1$ Mathematical equation copies of T in $B_{n + m} (X, Y)$ . Let H be the spanning subgraph of $B_{n + m} (X, Y)$ which contains all the edges that do not appear in the packing. It is easy to see that $e (H) = h_{1} h_{2} - (k_{1} + k_{2} - 1) (k - 1) .$ Since $(h_{1} - k_{1}) (h_{2} - k_{2}) + (h_{1} -$ Mathematical equation $k_{1}) + (h_{2} - k_{2}) \geq (k - 1) (n - 1)$ , we have $e (H) \geq k_{2} h_{1} + k_{1} h_{2}$ $+ k_{1} + k_{2} - h_{1} - h_{2} - k_{1} k_{2}$ . 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 $B_{n + m} (X, Y)$ Mathematical equation .

The proof is completed.

References

Woźniak M. Packing of graphs—A survey [J]. Discrete Mathematics, 2004, 276: 379-391. [CrossRef] [MathSciNet] [Google Scholar]
Yap H P. Packing of graphs—A survey [J]. Discrete Mathematics, 1988, 38: 395-404. [CrossRef] [MathSciNet] [Google Scholar]
Gyárfá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: 463-469. [Google Scholar]
Bollobás B. Some remarks on packing trees [J]. Discrete Mathematics, 1983, 46(2): 203-204. [CrossRef] [MathSciNet] [Google Scholar]
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]
Yuster R. On packing trees into complete bipartite graphs [J]. Discrete Mathematics, 1997, 163(1-3): 325-327. [CrossRef] [MathSciNet] [Google Scholar]
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]
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.

[R1] Woźniak M. Packing of graphs—A survey [J]. Discrete Mathematics, 2004, 276: 379-391. [CrossRef] [MathSciNet] [Google Scholar]

[R2] Yap H P. Packing of graphs—A survey [J]. Discrete Mathematics, 1988, 38: 395-404. [CrossRef] [MathSciNet] [Google Scholar]

[R3] Gyárfá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: 463-469. [Google Scholar]

[R4] Bollobás B. Some remarks on packing trees [J]. Discrete Mathematics, 1983, 46(2): 203-204. [CrossRef] [MathSciNet] [Google Scholar]

[R5] 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]

[R6] Yuster R. On packing trees into complete bipartite graphs [J]. Discrete Mathematics, 1997, 163(1-3): 325-327. [CrossRef] [MathSciNet] [Google Scholar]

[R7] 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]

[R8] Wang H. Packing two forests into a bipartite graph [J]. Journal of Graph Theory, 1996, 23(2): 209-213. [CrossRef] [MathSciNet] [Google Scholar]