Publication Date:
2015-10-29
Description:
Hypercubes and star graphs are widespread topologies of interconnection networks. The class of hyper-stars was introduced as a new type of interconnection network to compete with both hypercubes and star graphs, and the class of folded hyper-stars is a strengthened variation of hyper-stars with additional links to connect nodes with complemented 0/1-strings. Constructing independent spanning trees (ISTs) has numerous applications in networks such as fault-tolerant broadcasting and secure message distribution. Recently, Yang and Chang [IST on folded hyper-stars, Networks 56 (2010), 272–281] proposed an algorithm to construct $k+1$ ISTs on folded hyper-star $FHS(2k,k)$ . For $k\geqslant 4$ , their constructions include $k$ ISTs with a height $2k-2$ and the other one with a height $k+1$ . In this paper, we refine their constructed rules on $FHS(2k,k)$ for $k\geqslant 3$ and provide a set of constructions including $k$ ISTs with a height $k+2$ and the other one with a height $k+1$ . As a by-product, we obtain an improvement on the upper bound of the fault diameter (respectively, the wide diameter) of $FHS(2k,k)$ .
Print ISSN:
0010-4620
Electronic ISSN:
1460-2067
Topics:
Computer Science
Permalink