EMBEDDING LADDERS AND CATERPILLARS INTO THE HYPERCUBE

We present an embedding of generalized ladders as subgraphs into the h ypercube. Through an embedding of caterpillars into ladders, we obtain an embedding of caterpillars into the hypercube. In this way we get a lmost all known results concerning the embedding of caterpillars into the hypercube. In addition we construct an embedding for some new type s of caterpillars. Our results support the conjecture of Havel (1984). (C) 1998 Elsevier Science B.V. All rights reserved.