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.68149References:
[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.