Broadcasting secure messages via optimal independent spanning trees in folded hypercubes

Fault-tolerant broadcasting and secure message distribution are important issues for network applications. 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 security. An n-dimensional folded hypercube, denoted by FQ"n, is a strengthening variation of hypercube by adding additional links between nodes that have the furthest Hamming distance. In, [12], Ho(1990) proposed an algorithm for constructing n+1 edge-disjoint spanning trees each with a height twice the diameter of FQ"n. Yang et al. (2009), [29] recently proved that Ho's spanning trees are indeed independent, i.e., any two spanning trees have the same root, say r, and for any other node v r, the two different paths from v to r, one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce n+1 independent spanning trees of FQ"n, where the height of each tree is equal to the diameter of FQ"n plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal.