Packing 4-Partite Tree into Complete 4-Partite Graph

Yanling PENG

doi:10.1051/wujns/2024293239

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 Journal of Natural Sciences, 2024, Vol.29 No.3, 239-241

Mathematics

CLC number: O157.5

Packing 4-Partite Tree into Complete 4-Partite Graph

Yanling PENG

Department of Mathematics, Suzhou University of Science and Technology, Suzhou 215009, Jiangsu, China

Received: 20 June 2023

Abstract

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. Motivated by the "Tree Packing Conjecture" made by Gy $\dot{a}$ rf $\dot{a}$ s and Lehel, Wang Hong conjectured that for each k-partite tree, there is a packing of two copies of $T (X)$ into a complete k-partite graph $B_{n + m} (Y)$ , where $m = ⌊ k / 2 ⌋$ Mathematical equation . In this paper, we confirm this conjecture for $k = 4$ .

Key words: packing of graph / tree packing conjecture / embedding of graph

Cite this article: PENG Yanling. Packing 4-Partite Tree into Complete 4-Partite Graph[J]. Wuhan Univ J of Nat Sci, 2024, 29(3): 239-241.

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 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 $v$ Mathematical equation is a vertex adjacent to $v$ in G. $N_{G} (v)$ denotes the set of neighbors of a vertex $v$ in G. The degree of $v$ , denoted by $d e g_{G} (v)$ , is $| N_{G} (v) |$ . Given a subset A of $V (G)$ , $N_{G} (v, A)$ is $N_{G} (v) ⋂ A$ for the vertex $v \in V (G)$ . 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 $>$ Mathematical equation 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 $ϕ : 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 p-parking of G.

A k-partite graph G with the partition $X = (X_{1}, X_{2}, \dots, X_{k})$ Mathematical equation is denoted as $G (X_{1}, X_{2}, \dots, X_{k})$ or $G (X)$ . In this case, it is said that G admits the partition $X$ and $| X | = k$ . If G admits two distinct partitions $X$ and $Y$ , then the notion that $G (X) \neq G (Y)$ is adopted here. If G and H admit the k-partitions $X$ Mathematical equation and $Y$ , respectively, and $ϕ$ is an embedding of G into H such that $ϕ (X_{i}) \subset Y_{i}$ , then $ϕ$ is restrained and this is denoted as $ϕ : G (X) \to H (Y)$ . A packing $Φ = (ϕ_{1}, ϕ_{2}, \dots, ϕ_{p})$ of $G_{1} (X_{1}), G_{2} (X_{2}), \dots, G_{p} (X_{p})$ Mathematical equation into $H (Y)$ is restrained if each embedding of $Φ$ is restrained. A k-partite tree is a k-partite graph without cycles. Let $T (X)$ denote the k-partite tree with $X = (X_{1}, X_{2}, \dots, X_{k})$ as its k-partition and $B_{n} (Y)$ denote the complete k-partite graph of order n with $Y = (Y_{1}, Y_{2}, \dots, Y_{k})$ Mathematical equation 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 $T (X)$ Mathematical equation of order n, there is a restrained packing of two copies of $T (X)$ into a complete k-partite graph $B_{n + m} (Y)$ , where $m = ⌊ k / 2 ⌋$ .

This conjecture has been verified in Ref. [10] for $k = 2$ Mathematical equation . Recently, Sapozhnikov^[11] proved this conjecture with $k = 3$ , which is stated as the following proposition:

Proposition 1^[11] Let $T (X)$ Mathematical equation be a 3-partite tree of order n with partites $X_{1}, X_{2}, X_{3}$ . Then there exists a restrained 2-packing of $T (X)$ into a complete3-partite graph $B_{n + 1} (Y_{1}, Y_{2}, Y_{3})$ .

In this paper, we prove that the conjecture is true for $k = 4$ Mathematical equation .

1 Main Results

In the following lemmas, we assume that $T (X)$ Mathematical equation is a counter-example of Theorem 1 of minimum order n.

Lemma 1^[9] The endvertices of $T (X)$ Mathematical equation are adjacent to the same node if they are in the same partite.

Lemma 2^[9] If $v$ Mathematical equation is a node of $T (X)$ adjacent to endvertices in a partite $X$ , then $| X |$ is odd and $d e g (v, X) = (| X | + 1) / 2 .$

Theorem 1 For each 4-partite tree $T (X)$ Mathematical equation of order n with partition $X = (X_{1}, X_{2}, X_{3}, X_{4})$ , there is a restrained 2-packing of $T (X)$ into some complete 4-partite graph $B_{n + 2} (Y)$ .

Proof We assume that $T (X)$ Mathematical equation is a counter-example of Theorem 1 of minimum order n with partition $X = (X_{1}, X_{2}, X_{3}, X_{4})$ . Then $| X_{i} | > 1, i = 1,2, 3,4$ , since Theorem 1 holds if $| X_{i} | = 1$ for some i clearly.

If $T (X)$ Mathematical equation has exactly one node $v,$ then $T (X)$ is a star. So, for some i, $d e g (v, X_{i}) = | X_{i} | > 1$ . By Lemma 2, we have $d e g (v, X_{i}) = (| X_{i} | + 1) / 2 = | X_{i} |,$ a contradiction. Therefore, there are at least two nodes in $T (X)$ . By observing a longest path of $T (X)$ Mathematical equation , there exist at least two supernodes in $T (X)$ .

Let $v$ Mathematical equation be a supernode of $T (X)$ and $u$ be the only one non-endvertex adjacent to $v$ . Without loss of generality, we may assume that $v \in X_{1}$ . Let $V_{i} = N (v, X_{i}), i = 2,3, 4 .$ Then there is at least one of $V_{i}$ , $i = 2,3, 4,$ which is non-empty. Without loss of generality, we may assume that $V_{2} \neq \emptyset$ Mathematical equation . By Lemma 1, we can see that all the endvertices of $X_{2}$ are in the set $V_{2}$ . Let $V = X_{2} \ V_{2}$ . Then, $X_{2} = V_{2} ⋃ V$ and $| V_{2} | = | V | + 1$ by Lemma 2. So we may assume that $V_{2} = {v_{1}, v_{2}, \dots, v_{m}}$ and $V = {v_{m + 1}, v_{m + 2}, \dots, v_{2 m - 1}}$ Mathematical equation .

Consider the graph $T (X^{'}) = T (X) \ (X_{2} ⋃ {v}),$ Mathematical equation where $X^{'} = (X_{1}^{'}, X_{3}^{'}, X_{4}^{'})$ with $X_{1}^{'} = X_{1} \ {v}, X_{3}^{'} = X_{3}, X_{4}^{'} = X_{4}$ . So $T (X^{'})$ is a 3-partite tree with order $n^{'},$ where $n^{'} = n - 1 - | X_{2} |$ . By Proposition 1, there exists a restrained 2-packing $Φ^{'} = (ϕ_{1}^{'}, ϕ_{2}^{'})$ Mathematical equation of $T (X^{'})$ into a complete3-partite graph $B_{n^{'} + 1} (Y_{1}, Y_{3}, Y_{4})$ with $| X_{i}^{'} | \leq | Y_{i} |, i = 1,3, 4$ .

Suppose that there is $i \neq j$ Mathematical equation such that $V_{i} \neq \emptyset, V_{j} \neq \emptyset$ . Since $u$ be the only one non-endvertex adjacent to $v$ , without loss of generality, we may assume $u \notin X_{j}$ and $j = 2$ . Now add two vertices $x_{1}, x_{2}$ to $Y_{1}$ and a partite set $Y_{2}$ to $B_{n^{'} + 1} (Y_{1}, Y_{3}, Y_{4})$ Mathematical equation such that $| Y_{2} | = | X_{2} |$ . Let $Y_{2} = {y_{1}, y_{2}, \dots, y_{2 m - 1}} .$ Then the packing $Φ^{'}$ can be extended to $T (X)$ as follows: define $Φ (x) = Φ^{'} (x)$ for $x \in T (X^{'}),$ $ϕ_{1} (v) = x_{1},$ $ϕ_{2} (v) = x_{2}$ . Define $Φ (X_{2})$ Mathematical equation as follows:

$ϕ_{1} (v_{i}) = y_{i}$ Mathematical equation for $i = 1,2, \dots, 2 m - 1$ , $ϕ_{2} (v_{1}) = y_{1},$ $ϕ_{2} (v_{i}) = y_{2 m - i + 1}$ for $i = 2,3, \dots, 2 m - 1$ .

Thus, we extend the $Φ^{'}$ Mathematical equation to $T (X)$ so that a restrained 2-packing $Φ$ of $T (X)$ into the $B_{n + 2} (Y)$ is obtained, where $Y = (Y_{1} ⋃ {x_{1}, x_{2}}, Y_{2}, Y_{3}, Y_{4})$ , a contradiction.

Therefore, there exists only one nonempty $V_{i}$ Mathematical equation , which implies that all the endvertices adjacent to $v$ are in $V_{i}$ and $u \in V_{i} .$ Without loss of generality, we may assume that $i = 2$ and $u = v_{1}$ . Now add a vertex $x$ to $Y_{1}$ and add a partite set $Y_{2}$ to $B_{n^{'} + 1} (Y_{1}, Y_{3}, Y_{4})$ Mathematical equation such that $| Y_{2} | = | X_{2} | + 1$ . Let $Y_{2} = {y_{1}, y_{2}, \dots, y_{2 m}}$ . Then we extend the $Φ^{'}$ to $T (X)$ as follows:

Define $Φ (x) = Φ^{'} (x)$ Mathematical equation for $x \in T (X^{'})$ and $ϕ_{1} (v) = ϕ_{2} (v) = x$ . Define $Φ (X_{2})$ as follows: $ϕ_{1} (v_{i}) = y_{i}$ for $i = 1,2, \dots, 2 m - 1, ϕ_{2} (v_{i}) = y_{2 m - i + 1}$ for $i = 1,2, \dots, 2 m - 1$ . Thus, we extend $Φ^{'}$ to $T (X)$ so that a restrained 2-packing $Φ$ Mathematical equation of $T (X)$ into the $B_{n + 2} (Y)$ is obtained, where $Y = (Y_{1} ⋃ {x}, Y_{2}, Y_{3}, Y_{4})$ , 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) : 25-37. [MathSciNet] [Google Scholar]
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]
Peng Y L, Wang H. On packing trees into complete bipartite graphs[J]. Wuhan University Journal of Natural Sciences, 2023, 28(3): 221-222. [CrossRef] [EDP Sciences] [Google Scholar]
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]
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, 72: 395-404. [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: 463-469. [Google Scholar]
Bollobás B. Some remarks on packing trees[J]. Discrete Mathematics, 1983, 46(2): 203-204. [CrossRef] [MathSciNet] [Google Scholar]
Peng Y L, Wang H. Packing trees into complete k-partite graph[J]. Bulletin of the Korean Mathematical Society, 2022, 59(2): 345-350. [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]
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.

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

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

[R3] Peng Y L, Wang H. On packing trees into complete bipartite graphs[J]. Wuhan University Journal of Natural Sciences, 2023, 28(3): 221-222. [CrossRef] [EDP Sciences] [Google Scholar]

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

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

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

[R7] 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: 463-469. [Google Scholar]

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

[R9] Peng Y L, Wang H. Packing trees into complete k-partite graph[J]. Bulletin of the Korean Mathematical Society, 2022, 59(2): 345-350. [MathSciNet] [Google Scholar]

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

[R11] Sapozhnikov Y. Two Problems in 2-Packings of Graphs[D]. Moscow: University of Idaho, 2024. [Google Scholar]