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.

05C05 Trees