Title: Extended fault-tolerant bipanconnectivity and panconnectivity of folded hypercubes
Authors: Che-Nan Kuo; Chia-Wei Lee; Nai-Wen Chang; Kuang-Husn Shih
Addresses: Department of Digital Content Design and Management, TOKO University, No. 51, Sec. 2, University Road, Pu-Tzu City, ChiaYi County 61363, Taiwan ' Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan 70101, Taiwan ' Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan 70101, Taiwan ' Department of Digital Fashion Design, TOKO University, No. 51, Sec. 2, University Road, Pu-Tzu City, ChiaYi County 61363, Taiwan
Abstract: The folded hypercube (FQn for short) is a well-known variation of hypercube structure and can be constructed from a hypercube by adding a link to every pair of vertices with complementary addresses. FQn for any odd n is known to be bipartite. Let f be a faulty vertex in FQn, for n ≥ 2. In addition, let u and v be any two fault-free vertices in FQn − {f}. It has been shown that: 1) FQn − {f} contains a fault-free path P[u, v] of every length l with dFQn(u, v) + 2 ≤ l ≤ 2n − 3 and 2|l − dFQn (u, v), where n ≥ 2; 2) FQn − {f} contains a fault-free P[u, v] path of every length l with n − 1 ≤ l ≤ 2n − 3, where n ≥ 2 is even. In this paper, we extend the above-mentioned result to obtain two further properties as follows: 1) FQn − {f} contains a fault-free path P[u, v] of every length l with dFQn(u, v) ≤ l ≤ 2n − 3 and 2|l − dFQn(u, v) for n ≥ 2; 2) FQn − {f} contains a fault-free path P[u, v] of every length l with n − 1 ≤ l ≤ 2n − 2 for n ≥ 2 is even.
Keywords: folded hypercubes; interconnection networks; mobile communications; bipartite graphs; panconnectivity; bipanconnectivity; fault tolerance.
International Journal of Mobile Communications, 2014 Vol.12 No.4, pp.397 - 410
Published online: 30 Apr 2015 *
Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article