Embedding a subclass of trees into hypercubes

A long standing conjecture of Havel (1984) [10] states that every equipartite tree with maximum degree 3 on 2 n vertices is a spanning subgraph of the n -dimensional hypercube. The conjecture is known to be true for many subclasses of trees. Havel and Liebl (1986) [12] showed that every equipartite caterpillar with maximum degree 3 and having 2 n vertices is a spanning subgraph of the n -dimensional hypercube. Subsequently, Havel (1990) [11] remarked that the problem of verification of the conjecture for subdivisions of caterpillars with maximum degree 3 has remained open. In this paper, we show that a subdivision of a caterpillar with 2 n vertices and maximum degree 3 is a spanning subgraph of the n -dimensional hypercube if it is equipartite and has at most n − 3 vertices on the spine. The problem of embedding such trees that have spines of arbitrary length is still open.