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.
