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

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.


68M10 Network design and communication in computer systems
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.