The globally Bi-3*-connected property of the honeycomb rectangular torus

Abstract

The honeycomb rectangular torus is an attractive alternative to existing networks such as mesh-connected networks in parallel and distributed applications because of its low network cost and well-structured connectivity. Assume that m and n are positive even integers with n >= 4. It is known that every honeycomb rectangular torus HReT(m, n) is a 3-regular bipartite graph. We prove that in any HReT(m, n), there exist three internally-disjoint spanning paths joining x and y whenever x and y belong to different partite sets. Moreover, for any pair of vertices x and y in the same partite set, there exists a vertex z in the partite set not containing x and y, such that there exist three internally-disjoint spanning paths of G - {z} joining x and y. Furthermore, for any three vertices x, y, and z of the same partite set there exist three internally-disjoint spanning paths of G - {z} joining x and y if and only if n >= 6 or m = 2. (C) 2007 Elsevier Inc. All rights reserved.