The wide-diameter of then-dimensional toroidal mesh
Yoshiyasu Ishigami · Networks · 1996
In graph theory and a study of transmission delay and fault tolerance of networks, the connectivity and the diameter of a graph are very important and they have been studied by many mathematicians. We studied the wide-diameter of a k-regular k-connected graph which is defined by the maximum of the k-distance between two distinct vertices, when the k-distance between x and y is equal to the least number l such that there exists k vertex-disjoint paths between x and y whose lengths are at most l. Because the wide-diameter of any k-regular k-connected graph is greater than its diameter, a k-regular k-connected graph whose wide-diameter is equal to “1 + its diameter” is optimal. For example, it is known that the hypercube is such a graph. We define n-dimensional toroidal mesh C(d1, d2, ………, dn) with vertices {(x1, ………, xn)|0 ≤ xi < di (1 ≤ i ≤ n)}. Each vertex (x1, ………, xn) is adjacent to 2n other vertices: (x1 ± 1, x2, ………, xn), (x1, x2 ± 1, ………, xn), ………, (x1, x2, ………, xn ± 1), where additions are performed modulo di (1 ≤ i ≤ n). This graph is an n-dimensional orthogonal mesh with global edges, which is 2n-connected and 2n-regular. We show that the graph satisfies the above property with respect to its 2n-diameter and its diameter except for some special cases. © 1996 John Wiley & Sons, Inc.