Bibliographic Details
| Title: |
Embedding perfectly balanced 2-caterpillar into its optimal hypercube |
| Authors: |
Rajdeepak, Rishikant, Sunitha, V. |
| Publication Year: |
2021 |
| Collection: |
Computer Science
Mathematics |
| Subject Terms: |
Mathematics - Combinatorics, Computer Science - Discrete Mathematics |
| More Details: |
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\geq 1$, a $k$-caterpillar is a binary tree consisting of a path with $j$-caterpillars $(0\leq j\leq 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$. |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/2110.06165 |
| Accession Number: |
edsarx.2110.06165 |
| Database: |
arXiv |
