zbMATH — the first resource for mathematics

Spanning graphs of hypercubes: Starlike and double starlike trees. (English) Zbl 0992.05032
Summary: The aim of this paper is to prove that certain trees are spanning trees of the hypercube \(Q_n\). We introduce a new family of graphs which span hypercubes and we characterize the double starlike trees with maximum degree up to six that span a hypercube. We conclude by some open problems about spanning graphs and partitioning the hypercube into vertex-disjoint cycles of even length.

05C05 Trees
05C38 Paths and cycles
05C75 Structural characterization of families of graphs
Full Text: DOI