Embedding perfectly balanced 2-caterpillar into its optimal hypercube

Abstract

A long-standing conjecture on spanning trees of a hypercube states that a balanced tree on $2^n$ vertices with maximum degree at most $3$ spans the hypercube of dimension $n$ \cite{havel1986}. In this paper, we settle the conjecture for a special family of binary trees. A $0$-caterpillar is a path. For $k\ge 1$, a $k$-caterpillar is a binary tree consisting of a path with $j$-caterpillars $(0\le j\le k-1)$ emanating from some of the vertices on the path. A $k$-caterpillar that contains a perfect matching is said to be perfectly balanced. In this paper, we show that a perfectly balanced $2$-caterpillar on $2^n$ vertices spans the hypercube of dimension $n$.