AbstractFault‐tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple independent spanning trees (ISTs) as a broadcasting scheme or a distribution protocol for receiving high levels of fault‐tolerance and security. Recently, hyper‐stars were introduced as a competitive model of interconnection network for both hypercubes and star graphs. The class of folded hyper‐stars is a strengthened variation of hyper‐stars obtained by adding additional links to connect complemented nodes. Both hyper‐stars and folded hyper‐stars have been shown to have lower network cost (measured by the product of degree and diameter) than hypercubes, folded hypercubes, and other variants. In this article, we propose an algorithm to construct k + 1 ISTs on a regular folded hyper‐star FHS (2k,k), where the number of ISTs matches the connectivity of FHS(2k,k). In particular, for k > 4, the constructed k ISTs have height 2 k − 2, and the other one has height k + 1. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010