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

© Wuhan University 2024

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

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 non-endvertex 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 non-endvertex.

An embedding of a graph 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 p-parking of G.

A k-partite 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 k-partitions 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 k-partite tree is a k-partite graph without cycles. Let denote the k-partite tree with as its k-partition and denote the complete k-partite graph of order n with as its k-partition.

Packing problems are central to combinatorics. Many exciting results and elegant proofs of these results were obtained [1-4]. For a survey, see Refs. [5,6]. Among the best-known 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 k-partite tree of order n, there is a restrained packing of two copies of into a complete k-partite 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 3-partite tree of order n with partites . Then there exists a restrained 2-packing of into a complete3-partite graph .

In this paper, we prove that the conjecture is true for .

1 Main Results

In the following lemmas, we assume that is a counter-example 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 4-partite tree of order n with partition , there is a restrained 2-packing of into some complete 4-partite graph .

Proof   We assume that is a counter-example 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 non-endvertex adjacent to . Without loss of generality, we may assume that . Let Then there is at least one of , which is non-empty. 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 3-partite tree with order where . By Proposition 1, there exists a restrained 2-packing of into a complete3-partite graph with .

Suppose that there is such that . Since be the only one non-endvertex 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 2-packing 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 2-packing of into the is obtained, where , a contradiction.

The proof is completed.

References

  1. Wang H. Bipacking a bipartite graph with girth at least 12[J]. Journal of the Korean Mathematical Society, 2019, 56(1) : 25-37. [MathSciNet] [Google Scholar]
  2. Wang H, Sauer N. Packing three copies of a tree into a complete graph[J]. European Journal of Combinatorics, 1993,14: 137-142. [CrossRef] [MathSciNet] [Google Scholar]
  3. Peng Y L, Wang H. On packing trees into complete bipartite graphs[J]. Wuhan University Journal of Natural Sciences, 2023, 28(3): 221-222. [Google Scholar]
  4. Peng Y L, Wang H. On a conjecture of embeddable graphs[J]. Wuhan University Journal of Natural Sciences, 2021, 26(2): 123-127. [Google Scholar]
  5. WoŹniak M. Packing of graphs—A survey[J]. Discrete Mathematics, 2004, 276: 379-391. [CrossRef] [MathSciNet] [Google Scholar]
  6. Yap H P. Packing of graphs—a survey[J]. Discrete Mathematics, 1988, 72: 395-404. [CrossRef] [MathSciNet] [Google Scholar]
  7. 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]
  8. Bollobás B. Some remarks on packing trees[J]. Discrete Mathematics, 1983, 46(2): 203-204. [CrossRef] [MathSciNet] [Google Scholar]
  9. Peng Y L, Wang H. Packing trees into complete k-partite graph[J]. Bulletin of the Korean Mathematical Society, 2022, 59(2): 345-350. [Google Scholar]
  10. Wang H. Packing two forests into a bipartite graph[J]. Journal of Graph Theory, 1996, 23(2): 209-213. [CrossRef] [MathSciNet] [Google Scholar]
  11. Sapozhnikov Y. Two Problems in 2-Packings of Graphs[D]. Moscow: University of Idaho, 2024. [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.