Packing 4-Partite Tree into Complete 4-Partite Graph

Yanling PENG

doi:10.1051/wujns/2024293239

All issues

Volume 29 / No 3 (June 2024)

Wuhan Univ. J. Nat. Sci., 29 3 (2024) 239-241

Full HTML

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)$ 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}))$ 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 ⌋$ . 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: 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 $v$ 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 $>$ 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)$ 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}))$ 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})$ 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$ 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})$ 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})$ 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)$ 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$ . Recently, Sapozhnikov^[11] proved this conjecture with $k = 3$ , which is stated as the following proposition:

Proposition 1^[11] Let $T (X)$ 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$ .

1 Main Results

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

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

Lemma 2^[9] If $v$ 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)$ 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)$ 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)$ 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)$ , there exist at least two supernodes in $T (X)$ .

Let $v$ 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$ . 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}}$ .

Consider the graph $T (X^{'}) = T (X) \ (X_{2} ⋃ {v}),$ 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}^{'})$ 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$ 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})$ 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})$ as follows:

$ϕ_{1} (v_{i}) = y_{i}$ 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 $Φ^{'}$ 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}$ , 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})$ 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)$ 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 $Φ$ 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.

[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. [CrossRef] [EDP Sciences] [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] WoŹ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 [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. [MathSciNet] [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]