Spanning caterpillars of a hypercube

Spanning trees of the hypercube Q_n have been recently studied by several authors. In this paper, we construct spanning trees of Q_n which are caterpillars and establish quantitative bounds for a caterpillar to span Q_n. As a corollary, we disprove a conjecture of Harary and Lewinter on the length of the spine of a caterpillar spanning Qⁿ. © 1997 John Wiley & Sons, Inc.