The super-connected property of recursive circulant graphs |
| |
Authors: | Chang-Hsiung Tsai Jimmy JM Tan |
| |
Affiliation: | a Department of Computer Science and Information Engineering, Dahan Institute of Technology, Hualien 971, Taiwan, ROC b Department of Computer and Information Science, National Chiao Tung University, Hsinchu 300, Taiwan, ROC c Department of Information Engineering, Ta Hwa Institute of Technology, Hsinchu 307, Taiwan, ROC |
| |
Abstract: | In a graph G, a k-container Ck(u,v) is a set of k disjoint paths joining u and v. A k-container Ck(u,v) is k∗-container if every vertex of G is passed by some path in Ck(u,v). A graph G is k∗-connected if there exists a k∗-container between any two vertices. An m-regular graph G is super-connected if G is k∗-connected for any k with 1?k?m. In this paper, we prove that the recursive circulant graphs G(2m,4), proposed by Park and Chwa Theoret. Comput. Sci. 244 (2000) 35-62], are super-connected if and only if m≠2. |
| |
Keywords: | Super-connected Container Recursive circulant Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|