×

On ring embedding in hypercubes with faulty nodes and links. (English) Zbl 1339.68213

Summary: In this paper, we show that in an \(n\)-dimensional hypercube \(Q_n\) with \(f_n\) faulty nodes and \(f_e\) faulty edges, such that \(f_n+f_e\leqslant n-1\), a ring of length \(2^n-2f_n\) can be embedded avoiding the faulty elements when \(f_n >0\) or \(f_e<n-1\). When \(f_n = 0\) and \(f_e = n - 1\), if all the faulty edges are not incident on the same node, a Hamiltonian cycle can be embedded avoiding the faulty elements when \(n \geqslant 4\). For a \(Q_3\), however, if \(f_n = 0\) and \(f_e = 2\), a Hamiltonian cycle might not exist even when all faulty edges are not incident on the same node. We show that a ring of size 6 can be embedded in that case. When \(f_n = 0\) and \(f_e = n - 1\), if all the faulty edges are incident on the same node, clearly a Hamiltonian cycle cannot exist and we show that a ring of size \(2^n - 2\) can he embedded. This generalizes a recent result of Y.-C. Tseng [Inf. Process. Lett. 59, No. 4, 217–222 (1996; Zbl 0875.68149)] where the number of edge faults were assumed not to exceed \(n - 4\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
68M10 Network design and communication in computer systems
68M15 Reliability, testing and fault tolerance of networks and computer systems

Citations:

Zbl 0875.68149
Full Text: DOI

References:

[1] Chan, M.-Y.; Lee, S.-J., Distributed fault-tolerant embedding of rings in hypercubes, J. Parallel Distrib. Comput., 11, 63-71 (1991)
[2] Chen, M. S.; Shin, K. G., Processor allocation in an \(N\)-cube multiprocessor using gray codes, IEEE Trans. Comput., C-36, 1396-1407 (1987)
[3] Latifi, S.; Zheng, S.; Bagherzadeh, N., Optimal ring embedding in hypercubes with faulty links, (Proc. Fault-Tolerant Computing Symposium (1992)), 178-184
[4] Sen, A.; Sengupta, A.; Bandyopadhyay, S., On some topological properties of hypercube, incomplete hypercube and supercube, (Proc. International Parallel Processing Symposium. Proc. International Parallel Processing Symposium, Newport Beach (April, 1993)), 636-642
[5] Tseng, Y.-C.; Lai, T.-H., On the embedding of a class of regular graphs in a faulty hypercube, J. Parallel Distrib. Comput., 37, 2, 200-206 (1996) · Zbl 0859.68070
[6] Tseng, Y.-C., Embedding a ring in a hypercube with both both faulty links and faulty nodes, Inform. Process. Lett., 59, 217-222 (1996) · Zbl 0875.68149
[7] Yang, P.-J.; Tien, S.-B.; Raghavendra, C. S., Embedding of multidimensional meshes on to faulty hypercubes, (Proc. International Conference on Parallel Processing, Vol. 1 (1991)), 571-574
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.