Strong Menger connectivity with conditional faults on the class of hypercube-like networks. (English) Zbl 1186.68033

Shih, Lun-Min; Chiang, Chieh-Feng; Hsu, Lih-Hsing; Tan, Jimmy J. M.

Inf. Process. Lett. 106, No. 2, 64-69 (2008).

Summary: We study the Menger property on a class of hypercube-like networks. We show that in all \(n\)-dimensional hypercube-like networks with \(n - 2\) vertices removed, every pair of unremoved vertices \(u\) and \(v\) are connected by \(\min \{\deg (u),\deg (v)\}\) vertex-disjoint paths, where \(\deg (u)\) and \(\deg (v)\) are the remaining degree of vertices \(u\) and \(v\), respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to \(2n - 5\) vertex faults.

MSC:

68M10

Network design and communication in computer systems

Keywords:

strong Menger connectivity; conditional faults; hypercube-like network; interconnection networks

References:

[1]	Abraham, S.; Padmanabhan, K., The twisted cube topology for multiprocessors: a study in network asymmetry, Journal of parallel and distributed computing, 13, 104-110, (1991)
[2]	Cull, P.; Larson, S.M., The Möbius cubes, IEEE transactions on computers, 44, 647-659, (1995) · Zbl 1041.68522
[3]	Efe, K., The crossed cube architecture for parallel computing, IEEE transactions on parallel and distributed systems, 3, 513-524, (1992)
[4]	Esfahanian, A.H.; Ni, L.M.; Sagan, B.E., The twisted n-cube with application to multiprocessing, IEEE transactions on computers, 40, 88-93, (1991) · Zbl 1395.05139
[5]	Menger, K., Zur allgemeinen kurventheorie, Fund. math., 10, 95-115, (1927) · JFM 53.0561.01
[6]	E. Oh, On strong fault tolerance (or strong Menger-connectivity) of multicomputer networks, PhD thesis, Computer Science, Texas A&M University, August 2004. http://txspace.tamu.edu/bitstream/1969.1/1284/1/etd-tamu-2004B-CPSC-Oh-2.pdf
[7]	Oh, E.; Chen, J., On strong Menger-connectivity of star graphs, Discrete applied mathematics, 129, 499-511, (2003) · Zbl 1032.05076
[8]	Oh, E.; Chen, J., Strong fault-tolerance: parallel routing in star networks with faults, Journal of interconnection networks, 4, 113-126, (2003)
[9]	A.S. Vaidya, P.S.N. Rao, S.R. Shankar, A class of hypercube-like networks, in: Proc. of the 5th Symp. IEEE Transactions on Parallel and Distributed Processing, Soc., Los Alamitos, CA, 1993, pp. 800-803