Article ID Journal Published Year Pages File Type
395244 Information Sciences 2007 17 Pages PDF
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)(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.

Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
, , ,