Labeled packing of non star trees into their \(k\) th power, \(k\geq 5\) (Q6562431)

In this paper, the authors deal with a certain type of graph packing problems. A \(2\)-placement of a graph \(G\) is an isomorphism \(\sigma\) of \(G\) to a subgraph of \(\overline{G}\), the complement of \(G\). It is a well-known fact that every non-star tree admits a \(2\)-placement. Then there is a study in which we introduce a constraint on the distance and discuss the existence of a \(2\)-placement under this constraint. Let \(d_G(x, y)\) be the distance between vertices \(x\) and \(y\) in a graph \(G\), and let \(G^k\) be the graph obtained from \(G\) by adding edges between every pair of vertices of distance at most \(k\). \N\N\textit{M. Woźniak} [in: Sets, graphs and numbers. A birthday salute to Vera T. Sós and András Hajnal. Amsterdam: North-Holland Publishing Company. 727--732 (1992; Zbl 0785.05030)] proved that every non-star tree \(T\) admits a \(2\)-placement \(\sigma\) with \(\sigma(T)\subset T^7\). Then \textit{H. Kheddouci} et al. [Discrete Math. 213, No. 1--3, 169--178 (2000; Zbl 0956.05080)] improved this result and proved that for every non-star tree \(T\) and every vertex \(x\) in \(T\), there exists a \(2\)-placement \(\sigma\) of \(T\) satisfying (1)~\(\sigma(T)\subset T^4\), (2)~\(d_T(x, \sigma(x))=1\) and (3)~\(d_T(y, \sigma(y))\le 2\) holds for every neighbor \(y\) of \(x\). \N\NIn this paper, the authors prove that they can impose a condition on vertices not in the neighborhood of a prescribed vertex \(x\). They prove that for every tree \(T\) and every vertex \(x\) in \(T\), there exists a \(2\)-placement \(\sigma\) such that (1)~\(\sigma(T)\subset T^5\), (2)~\(\sigma(v)\ne v\) holds for every vertex \(v\) in \(T\), (3)~\(d_T(x, \sigma(x))\le 2\), (4)~\(d_T(y, \sigma_T(y))\le 3\) holds for every neighbor \(y\) of \(x\) and (5)~\(d_T(z, \sigma(z))\le 4\) holds for every non-neighbor \(z\) of \(x\). Then the authors apply this result to study a labeled version of \(2\)-placement, in which \(V(T)\) is assigned a (non necessarily one-to-one) labeling, and they seek for a \(2\)-placement under the constraint that every vertex has to be mapped to a vertex of the same label.