A graph H of order n is said to be embeddable in a graph G of order n, if G contains a spanning subgraph isomorphic to H. It is well known that any non-star tree T of order n is embeddable in its complement (i.e. in K_n - E(T)). In the paper "Packing two copies of a tree into its fourth power" by Hamamache Kheddouci, Jean-Francois Sacle, and Mariusz Wozniak, Discrete Mathematics 213 (2000), 169-178, it is proved that any non-star tree T is embeddable in T~4 - E(T). They asked whether every non-star tree T is embeddable in T~3 - E(T). In this paper, answering their question negatively, we show that there exist trees T such that T is not embeddable in T~3 - E(T).
展开▼
