The Wide Diameters of Regular Hyper-Stars and Folded Hyper-Stars. (7th June 2017)

• Record Type: Journal Article
• Authors: Chang, Jou-Ming; Yang, Jinn-Shyong; Tang, Shyue-Ming; Pai, Kung-Jui
• Is Part Of: Computer journal. Volume 61:Number 1(2018)
• Page Start: 121
• Page End: 128
• Publication Date: 2017-06-07
• Subjects: interconnection networks -- fault diameter -- wide diameter -- regular hyper-stars -- folded hyper-stars -- independent spanning trees; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx053
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: In this paper, we determine the wide diameters of regular hyper-stars HS ( 2 k, k ) and folded hyper-stars FHS ( 2 k, k ) . We first provide a connection between the wide diameter and the maximum height of a set of particular spanning trees, called independent spanning trees (ISTs for short), of a graph. According to this relation, we analyze the heights of ISTs constructed in the previous works to establish upper bounds of the wide diameters of HS ( 2 k, k ) and FHS ( 2 k, k ) . By contrast, we take the known results of fault diameters of HS ( 2 k, k ) and FHS ( 2 k, k ) as lower bounds. Consequently, we obtain the following results: (i) D w ( HS ( 2 k, k ) ) = 2 k + 1 for k ≥ 2, and (ii) D w ( FHS ( 4, 2 ) ) = 3 and D w ( FHS ( 2 k, k ) ) = k + 2 for k ≥ 3, where D w ( G ) stands for the wide diameter of a graph G . The latter gives the answer of a question arisen from a previous work [(2015) Pruning longer branches of ISTs on folded hyper-stars, Comput. J., 58, 2972–2981]. In addition, we ascertain that all ISTs of HS ( 2 k, k ) and FHS ( 2 k, k ) constructed in the previous works are optimal in the sense that their heights are minimized.