Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
395244 | Information Sciences | 2007 | 17 Pages |
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)(m,n) is a 3-regular bipartite graph. We prove that in any HReT(m,n)(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}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}G-{z} joining x and y if and only if n ⩾ 6 or m = 2.