Packing three copies of a tree into its sixth power (Q2243090): Difference between revisions

In this paper, the authors consider the problem of packing multiple copies of a tree into its power. \par A packing of graphs \(H_1, H_2,\dots, H_k\) into a graph \(G\) is a set of edge-disjoint subgraphs \(G_1, G_2,\dots, G_k\) of \(G\) with \(G_i\simeq H_i\) for each \(i\) with \(1\le i\le k\). In a special case of \(H_1=H_2=\dots=H_k=H\), we call it a packing of \(k\) copies of \(H\) into \(G\), and if \(k=1\) and \(H_1=H\), we call it an embedding of \(H\) into \(G\). \textit{D. Burns} and \textit{S. Schuster} [J. Graph Theory 1, 277--279 (1977; Zbl 0375.05046)] and \textit{N. Sauer} and \textit{J. Spencer} [J. Comb. Theory, Ser. B 25, 295--302 (1978; Zbl 0417.05037)] independently proved that every graph \(H\) with \(|E(H)|\le |V(H)|-2\) can be embedded into \(\overline{H}\), the complement of \(H\). Since a star cannot be embedded into its complement, we cannot replace the hypothesis of \(|E(H)|\le |V(H)|-2\) with \(|E(H)|\le |V(H)|-1\). Actually, \textit{D. Burns} and \textit{S. Schuster} [Isr. J. Math. 30, 313--320 (1978; Zbl 0379.05023)] characterized the graphs \(H\) with \(|E(H)|=|V(H)|-1\) that cannot be embedded into \(\overline{H}\). In their characterization, the stars are the only connected graphs. Therefore, their result implies that every tree which is not a star, referred as a non-star tree, can be embedded into its complement. \par The above researches were extended in two directions. In one direction, we interpret an embedding of \(H\) into \(\overline{H}\) as an embedding of \(H\) into \(K_n-E(H)\), where \(n=|V(H)|\), and replace \(K_n\) with a given graph \(G\). Hence we try to pack one or more copies of \(H\) into \(G-E(H)\). In the other direction, we interpret an embedding of \(H\) into \(\overline{H}\) as a packing of two copies of \(H\) into \(K_n\), and try to pack two or more copies into \(G\). In both directions, the case in which \(H\) is a tree and \(G=H^k\) is of main interest, where \(H^k\) is the graph obtained from \(H\) by adding an edge between every pair of vertices of distance at most \(k\). Note that if we can pack \(m\) copies of a tree \(T\) of order \(n\) into \(T^k-E(T)\), then we can pack \(m+1\) copies of \(T\) into \(T^k\), but the converse is not guaranteed. However, if \(k=n-1\), then \(T^{n-1}=K_n\) and the converse holds. Therefore, in the case of \(k=n-1\), there is no difference in both directions. \par As a result in the first direction, \textit{H. Kheddouci} et al. [Discrete Math. 213, No. 1--3, 169--178 (2000; Zbl 0956.05080)] proved that every non-star tree \(T\) of order at least \(4\) can be embedded into \(T^4-E(T)\). They also conjectured that actually \(T\) can be embedded into \(T^3-E(T)\). However, \textit{K. Suzuki} [Ars Comb. 73, 23--31 (2004; Zbl 1078.05073)] disproved the conjecture. Then as a result in the second direction, \textit{A. Kaneko} and \textit{K. Suzuki} [Discrete Math. 306, No. 21, 2779--2785 (2006; Zbl 1103.05066)] proved that for every non-star tree \(T\), two copies of \(T\) can be packed into \(T^3\). \par In this paper, the authors prove that if \(T\) is a tree of diameter at least~\(5\), then two copies of \(T\) can be packed into \(T^6-E(T)\). The hypothesis on the diameter cannot be relaxed. For example, \(P_5\), the path of order~\(5\), has diameter~\(4\) and has \(4\) edges. Also \((P_5)^6=K_5\), which has only \(10\) edges. Therefore, we cannot even pack three copies of \(P_5\) into its sixth power.