# zbMATH — the first resource for mathematics

On two-legged caterpillars which span hypercubes. (English) Zbl 0692.05023
Combinatorics, graph theory, and computing, Proc. 19th Southeast. Conf., Boca Raton/Fla. 1988, Congr. Numerantium 66, 103-108 (1988).
Summary: [For the entire collection see Zbl 0665.00002.]
A caterpillar is a tree which becomes a path when its endnodes are removed. A two-legged caterpillar has maximum degree four. A strictly two-legged caterpillar has degree set $$\{$$ 1,2,4$$\}$$. While a characterization of the two-legged caterpillars on $$2^ n$$ nodes which span a hypercube $$Q_ n$$ is at present unknown, we present classes of strictly two-legged caterpillars which span hypercubes. A tight upper bound is given for the number of nodes of degree four in strictly two- legged caterpillars which span a hypercube.

##### MSC:
 05C05 Trees
##### Keywords:
two-legged caterpillar
Zbl 0665.00002