Computing the Wide Diameter of Regular Hyper-Star Networks Using Independent Spanning Trees

Abstract

In this paper, we determine the wide diameter of a regular hyper-star network HS (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 network. According to this relation, we analyze the height of a set of constructed ISTs in HS (2k,k) to establish an upper bound of the wide diameter of HS(2k,k). By contrast, we take the known result of fault diameter of HS (2k,k) as a lower bound. As a consequence, we obtain the following result: Dw(HS(2k,k))=2k+1 for k≥2, where Dw(G) stands for the wide diameter of a graph G.