Harary, Frank; Lewinter, Martin; Widulski, William 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. Cited in 5 Documents MSC: 05C05 Trees Keywords:two-legged caterpillar Citations:Zbl 0665.00002 PDFBibTeX XML