Embedding perfectly balanced 2-caterpillar into its optimal hypercube

MaRDI QIDQ6380105zbMATH OpenFDO

Authors Rishikant Rajdeepak, V. Sunitha

Publication date 12 October 2021

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 $kgeq1$, a $k$-caterpillar is a binary tree consisting of a path with $j$-caterpillars $(0leqjleqk-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$.

This page was built for publication: Embedding perfectly balanced 2-caterpillar into its optimal hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380105)