Issue 
Wuhan Univ. J. Nat. Sci.
Volume 29, Number 3, June 2024



Page(s)  239  241  
DOI  https://doi.org/10.1051/wujns/2024293239  
Published online  03 July 2024 
Mathematics
CLC number: O157.5
Packing 4Partite Tree into Complete 4Partite Graph
Department of Mathematics, Suzhou University of Science and Technology, Suzhou 215009, Jiangsu, China
Received:
20
June
2023
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. Motivated by the "Tree Packing Conjecture" made by Gyrfs and Lehel, Wang Hong conjectured that for each kpartite tree, there is a packing of two copies of into a complete kpartite graph , where . In this paper, we confirm this conjecture for .
Key words: packing of graph / tree packing conjecture / embedding of graph
Cite this article: PENG Yanling. Packing 4Partite Tree into Complete 4Partite Graph[J]. Wuhan Univ J of Nat Sci, 2024, 29(3): 239241.
Biography: PENG Yanling, female, Professor, research direction: Graph Theory. Email: pengyanling@usts.edu.cn
Fundation item: Supported by the National Natural Science Foundation of China (12071334)
© Wuhan University 2024
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
We shall use standard graph theory notation. For any graph G, a neighbor of a vertex is a vertex adjacent to in G. denotes the set of neighbors of a vertex in G. The degree of , denoted by , is . Given a subset A of , is for the vertex . When the context is clear, the subscript G is omitted.
An endvertex is a vertex of degree 1 and nonendvertex is a vertex of degree 1. A node is a vertex adjacent to an endvertex. A supernode is a node x of G such that, with one exception, every neighbor of x is an endvertex. A star is a treewith only one nonendvertex.
An embedding of a graph 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 pparking of G.
A kpartite graph G with the partition is denoted as or . In this case, it is said that G admits the partition and . If G admits two distinct partitions and , then the notion that is adopted here. If G and H admit the kpartitions and , respectively, and is an embedding of G into H such that , then is restrained and this is denoted as . A packing of into is restrained if each embedding of is restrained. A kpartite tree is a kpartite graph without cycles. Let denote the kpartite tree with as its kpartition and denote the complete kpartite graph of order n with as its kpartition.
Packing problems are central to combinatorics. Many exciting results and elegant proofs of these results were obtained^{ [14]}. For a survey, see Refs. [5,6]. Among the bestknown packing problems, the famous Tree Packing Conjecture of Gyárfás and Lehel^{ [7]} has driven a large amount of research in the area. Bollobás^{ [8]} confirmed the "Tree Packing Conjecture" for many small trees. Motivated by the "Tree Packing Conjecture", Wang Hong made the following conjecture:
Conjecture^{[9]} For each kpartite tree of order n, there is a restrained packing of two copies of into a complete kpartite graph , where .
This conjecture has been verified in Ref. [10] for . Recently, Sapozhnikov^{[11]} proved this conjecture with , which is stated as the following proposition:
Proposition 1^{[11]} Let be a 3partite tree of order n with partites . Then there exists a restrained 2packing of into a complete3partite graph .
In this paper, we prove that the conjecture is true for .
1 Main Results
In the following lemmas, we assume that is a counterexample of Theorem 1 of minimum order n.
Lemma 1^{[9]} The endvertices of are adjacent to the same node if they are in the same partite.
Lemma 2^{[9]} If is a node of adjacent to endvertices in a partite , then is odd and
Theorem 1 For each 4partite tree of order n with partition , there is a restrained 2packing of into some complete 4partite graph .
Proof We assume that is a counterexample of Theorem 1 of minimum order n with partition . Then , since Theorem 1 holds if for some i clearly.
If has exactly one node then is a star. So, for some i, . By Lemma 2, we have a contradiction. Therefore, there are at least two nodes in . By observing a longest path of , there exist at least two supernodes in .
Let be a supernode of and be the only one nonendvertex adjacent to . Without loss of generality, we may assume that . Let Then there is at least one of , which is nonempty. Without loss of generality, we may assume that . By Lemma 1, we can see that all the endvertices of are in the set . Let . Then, and by Lemma 2. So we may assume that and .
Consider the graph where with . So is a 3partite tree with order where . By Proposition 1, there exists a restrained 2packing of into a complete3partite graph with .
Suppose that there is such that . Since be the only one nonendvertex adjacent to , without loss of generality, we may assume and . Now add two vertices to and a partite set to such that . Let Then the packing can be extended to as follows: define for . Define as follows:
for , for .
Thus, we extend the to so that a restrained 2packing of into the is obtained, where , a contradiction.
Therefore, there exists only one nonempty , which implies that all the endvertices adjacent to are in and Without loss of generality, we may assume that and . Now add a vertex to and add a partite set to such that . Let . Then we extend the to as follows:
Define for and . Define as follows: for for . Thus, we extend to so that a restrained 2packing of into the is obtained, where , a contradiction.
The proof is completed.
References
 Wang H. Bipacking a bipartite graph with girth at least 12[J]. Journal of the Korean Mathematical Society, 2019, 56(1) : 2537. [MathSciNet] [Google Scholar]
 Wang H, Sauer N. Packing three copies of a tree into a complete graph[J]. European Journal of Combinatorics, 1993,14: 137142. [CrossRef] [MathSciNet] [Google Scholar]
 Peng Y L, Wang H. On packing trees into complete bipartite graphs[J]. Wuhan University Journal of Natural Sciences, 2023, 28(3): 221222. [Google Scholar]
 Peng Y L, Wang H. On a conjecture of embeddable graphs[J]. Wuhan University Journal of Natural Sciences, 2021, 26(2): 123127. [Google Scholar]
 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, 72: 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]
 Peng Y L, Wang H. Packing trees into complete kpartite graph[J]. Bulletin of the Korean Mathematical Society, 2022, 59(2): 345350. [Google Scholar]
 Wang H. Packing two forests into a bipartite graph[J]. Journal of Graph Theory, 1996, 23(2): 209213. [CrossRef] [MathSciNet] [Google Scholar]
 Sapozhnikov Y. Two Problems in 2Packings of Graphs[D]. Moscow: University of Idaho, 2024. [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.