標題: | 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-十二月-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 |
顯示於類別: | 期刊論文 |