Embedding a subclass of trees into hypercubes

AbstractA long standing conjecture of Havel (1984) [10] states that every equipartite tree with maximum degree 3 on 2n 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 2n 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 2n 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