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.

In this paper, we propose a new class of graphs called generalized recursive circulant graphs which is an extension of recursive circulant graphs. While retaining attractive properties of recursive circulant graphs, the new class of graphs achieve more flexibility in varying the number of vertices. Some network properties of recursive circulant graphs, like degree, connectivity and diameter, are adapted to the new graph class with more concise expression. In particular, we use a multidimensional vertex labeling scheme in generalized recursive circulant graphs. Based on the labeling scheme, a shortest path routing algorithm for the graph class is proposed. The correctness of the routing algorithm is also proved in this paper.

Two spanning trees rooted at vertex r in a graph G are called independent spanning trees (ISTs) if for each vertex v in G, vner, the paths from vertex v to vertex r in these two trees are internally distinct. If the connectivity of G is k, the IST problem is to construct k ISTs rooted at each vertex. The IST problem has found applications in fault-tolerant broadcasting, but it is still open for general graphs with connectivity greater than four. In this paper, we shall propose a very simple algorithm for solving the IST problem on multidimensional torus networks. In our algorithm, every vertex can determine its parent for a specific independent spanning tree only depending on its own label. Thus, our algorithm can also be implemented in parallel systems or distributed systems very easily.