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. (C) 2011 Elsevier B.V. All rights reserved.