zbMATH — the first resource for mathematics

Spanning caterpillars of a hypercube. (English) Zbl 0865.05034
A hypercube \(Q_n\) is a graph whose vertex set consists of all binary vectors of size \(n\), with an edge joining two vectors if and only if they differ in exactly one coordinate. A caterpillar is a tree with at least three vertices that becomes a path when its endvertices are removed. Then finding a spanning caterpillar of a hypercube can be interpreted as finding a path so that each vertex in the hypercube is in the path or is adjacent to one in the path. The paper discusses the problem of determining the length of the shortest such paths. Particularly, it is shown that \[ {2^n\over n}\leq s_n\leq 4\cdot{2^n\over n}, \] where \(s_n\) is the number of vertices in such a path.

05C05 Trees
05C38 Paths and cycles
Full Text: DOI