Broadcasting secure messages via optimal independent spanning trees in folded hypercubes

Abstract: 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 -dimensional folded hypercube, denoted by , is a strengthening variation of hypercube by adding additional links between nodes that have the furthest Hamming distance. In, , Ho(1990) proposed an algorithm for constructing edge-disjoint spanning trees each with a height twice the diameter of . Yang et al. (2009), recently proved that Ho’s spanning trees are indeed independent, i.e., any two spanning trees have the same root, say , and for any other node , the two different paths from to , one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce independent spanning trees of , where the height of each tree is equal to the diameter of plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal. [Copyright &y& Elsevier]