The Wide Diameters of Regular Hyper-Stars and Folded Hyper-Stars. (7th June 2017) - Chang, Jou-Ming; Yang, Jinn-Shyong; Tang, Shyue-Ming; Pai, Kung-Jui
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.