The Wide Diameters of Regular Hyper-Stars and Folded Hyper-Stars.

In this paper, we determine the wide diameters of regular hyper-stars HS(2k, k) and folded hyper-stars FHS(2k, 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(2k, k) and FHS(2k, k). By contrast, we take the known results of fault diameters of HS(2k, k) and FHS(2k, k) as lower bounds. Consequently, we obtain the following results: (i) Dw (HS(2k, k)) = 2k + 1 for k ≥ 2, and (ii) Dw (FHS(4, 2)) = 3 and Dw (FHS(2k, k)) = k + 2 for k ≥ 3, where Dw (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(2k, k) and FHS(2k, k) constructed in the previous works are optimal in the sense that their heights are minimized. [ABSTRACT FROM AUTHOR]