Topological properties have become a popular and important area of focus for studies that analyze interconnections between networks. The hypercube is one of the most widely discussed topological structures for interconnections between networks and is usually covered in introductions to the basic principles and methods for network design. The exchanged hypercube EH(s, t) is a new variant of the hypercube that has slightly more than half as many edges and retains several valuable and desirable properties of the hypercube. In this paper, we propose an approach for shortest path routing algorithms from the source vertex to the destination vertex in EH(s, t) with time complexity O(n), where n = s + t + 1 and 1 ≤ s ≤ t. We focus on edge congestion, which is an important indicator for cost analyses and performance measurements in interconnection networks. Based on our shortest path routing algorithm, we show that the edge congestion of EH(s, t) is 3 · 2s+t+1- 2s+1- 2t+1. In addition, we prove that our shortest path routing algorithm is an optimal routing strategy with respect to the edge congestion of EH(s, t).

The n-dimensional hypercube is one of the most popular topological structure for interconnection networks in parallel computing and communication systems. The exchanged hypercube EH(s, t), a variant of the hypercube, retains several valuable and desirable properties of the hypercube such as a small diameter, bipancyclicity, and super connectivity. In this paper, we construct s + 1 (or t + 1) internally vertex-disjoint paths between any two vertices for parallel routes in the exchanged hypercube EH(s, t) for 3 ≤ s ≤ t. We also show that both the (s + 1)-wide diameter and s-fault diameter of the exchanged hypercube EH(s, t) are s + t + 3 for 3 ≤ s ≤ t.

Diagnosability of a system directly refers to the maximum number of faulty vertices that can be identified by the system. Somani et al. [2] proposed a generalized measure to increase the degree of diagnosability of the hypercubes and star graphs. This paper provides counterexamples for the results of diagnosability of star graphs.