Spanning caterpillars of hypercube
Dvorak, T., Havel, I., Laborde, J.M., Mollard, M., Informatique et Mathematiques Appliquees de Grenoble (IMAG), 38 - Saint-Martin-d'Heres (France). Lab. Structures Discretes et Didactique (LSD), Institut National Polytechnique de Grenoble (INPG), 38 - Grenoble (France). Lab. Structures Discretes et Didactique (LSD) · OpenGrey (Institut de l'Information Scientifique et Technique) · 1995
Spanning trees of the hypercube Qn have been recently studied by several authors. In this paper, we construct spanning trees of Qn which are caterpillars and establish quantitative bounds for a caterpillar to span Qn. As a corollary, we disprove a conjecture of Harary and Lewinter on the length of the spine of a caterpillar spanning Qn. © 1997 John Wiley & Sons, Inc.