2021/10/12 by Rajdeepak, Rishikant, Sunitha, V.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2110.06165
A long-standing conjecture on spanning trees of a hypercube states that a balanced tree on 2n vertices with maximum degree at most 3 spans the hypercube of dimension n \citehavel1986. In this paper, we settle the conjecture for a special family of binary trees. A 0-caterpillar is a path. For k≥ 1, a k-caterpillar is a binary tree consisting of a path with j-caterpillars (0≤ j≤ 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 2n vertices spans the hypercube of dimension n.