A Counterexample to a Conjecture on Packing Two Copies of a Tree into its Third Power

Abstract

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 Saclé, and Mariusz Wodgniak, 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)$.