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 nn-dimensional folded hypercube, denoted by FQnFQn, 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+1n+1 edge-disjoint spanning trees each with a height twice the diameter of FQnFQn. 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 rr, and for any other node v≠rv≠r, the two different paths from vv to rr, one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce n+1n+1 independent spanning trees of FQnFQn, where the height of each tree is equal to the diameter of FQnFQn plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal.