標題: The globally Bi-3*-connected property of the honeycomb rectangular torus
作者: Teng, Yuan-Hsiang
Tan, Jimmy J. M.
Hsu, Lih-Hsing
資訊工程學系
Department of Computer Science
關鍵字: Hamiltonian;honeycomb torus;connectivity
公開日期: 15-Dec-2007
摘要: 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.
URI: http://dx.doi.org/10.1016/j.ins.2007.06.016
http://hdl.handle.net/11536/10007
ISSN: 0020-0255
DOI: 10.1016/j.ins.2007.06.016
期刊: INFORMATION SCIENCES
Volume: 177
Issue: 24
起始頁: 5573
結束頁: 5589
Appears in Collections:Articles


Files in This Item:

  1. 000250899400005.pdf