Independent Spanning Trees on Folded Hypercubes

Fault-tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and of security. A set of spanning trees in a graph is said to be edge-disjoint if they are rooted at the same node without sharing any common edge. A folded hypercube is a strengthened variation of hypercube obtained by adding additional links between nodes that are Hamming distance furthest apart. Ho [C.-T. Ho, Full bandwidth communications on folded hypercubes, in Proc. 1990 International conference on Parallel Processing, vol. 1, 1990, pp. 267-280] presented an algorithm for constructing n + 1 edge-disjoint spanning trees in an n-dimensional folded hypercube. In this paper, we prove that indeed all spanning trees constructed by this algorithm are independent, i.e., any two spanning trees have the same root, say r, and for any other node u ¿ r, the two different paths from u to r, one path in each tree, are internally node-disjoint.