No Access

Hamiltonian Cycle Embeddings in Faulty Hypercubes Under the Forbidden Faulty Set Model

Chunfang Li

https://orcid.org/0000-0002-6210-2593

School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, P. R. China

E-mail Address: chunfangli@sxu.edu.cn

Corresponding author.

Search for more papers by this author

Shangwei Lin

School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, P. R. China

E-mail Address: shangweilin@sxu.edu.cn

Search for more papers by this author

, and

Shengjia Li

School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, P. R. China

E-mail Address: shjiali@sxu.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0129054121500039Cited by:3 (Source: Crossref)

Abstract

In this paper, we study the fault-tolerant capability of hypercubes with respect to the hamiltonian property based on the concept of forbidden faulty sets. We show, with the assumption that each vertex is incident with at least three fault-free edges, that an $n$ -dimensional hypercube contains a fault-free hamiltonian cycle, even if there are up to $(4 n - 13)$ edge faults. Moreover, we give an example to show that the result is optimal with respect to the number of edge faults tolerated.

This work is supported by the National Natural Science Foundation of China (11701349).

Communicated by Hsu-Chun Yen

Keywords:

References

1. S. G. Akl, Parallel Computation: Models and Methods (Prentice Hall, NJ, 1997). Google Scholar
2. M. Y. Chan and S. J. Lee, On the existence of Hamiltonian circuits in faulty hypercubes, SIAM J. Discr. Math. 4 (1991) 511–527. Crossref, Web of Science, Google Scholar
3. J.-C. Chen and C.-H. Tsai, Conditional edge-fault-tolerant Hamiltonicity of dual-cubes, Inform. Sci. 181 (2011) 620–627. Crossref, Web of Science, Google Scholar
4. D. Cheng and R.-X. Hao, Various cycles embedding in faulty balanced hypercubes, Inform. Sci. 297 (2015) 140–153. Crossref, Web of Science, Google Scholar
5. D. Cheng, R.-X. Hao and Y.-Q. Feng, Conditional edge-fault pancyclicity of augmented cubes, Theor. Comput. Sci. 510 (2013) 94–101. Crossref, Web of Science, Google Scholar
6. D. Cheng, R.-X. Hao and Y.-Q. Feng, Vertex-fault-tolerant cycles embedding in balanced hypercubes, Inform. Sci. 288 (2014) 449–461. Crossref, Web of Science, Google Scholar
7. A. H. Esfahanian, Generalized measures of fault-tolerance with application to $n$ -cube networks, IEEE Trans. Comput. 38 (1989) 1586–1591. Crossref, Web of Science, Google Scholar
8. J. S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Comput. 29 (2003) 821–832. Crossref, Web of Science, Google Scholar
9. J. S. Fu, Longest fault-free paths in hypercubes with vertex faults, Inform. Sci. 176 (2006) 759–771. Crossref, Web of Science, Google Scholar
10. J.-S. Fu, Fault-free Hamiltonian cycles in twisted cubes with conditional link faults, Theor. Comput. Sci. 407 (2008) 318–329. Crossref, Web of Science, Google Scholar
11. J. Guo, D. Li and M. Lu, The $g$ -good-neighbor conditional diagnosability of the crossed cubes under the PMC and MM* model, Theor. Comput. Sci. 755 (2019) 81–88. Crossref, Web of Science, Google Scholar
12. R.-X. Hao, R. Zhang, Y.-Q. Feng and J.-X. Zhou, Hamiltonian cycle embedding for fault tolerance in balanced hypercubes, Appl. Math. Comput. 244 (2014) 447–456. Crossref, Web of Science, Google Scholar
13. S. He, R.-X. Hao and E. Cheng, Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks, Theor. Comput. Sci. 731 (2018) 50–67. Crossref, Web of Science, Google Scholar
14. S.-Y. Hsieh, C.-W. Lee and C.-H. Huang, Conditional edge-fault hamiltonian-connectivity of restricted hypercube-like networks, Inform. Comput. 251 (2016) 314–334. Crossref, Web of Science, Google Scholar
15. X. Hu, H. Liu and X.-F. Pan, Fault-free Hamilton cycles in burnt pancake graphs with conditional edge faults, Discr. Appl. Math. 169 (2014) 152–161. Crossref, Web of Science, Google Scholar
16. H.-S. Hung, J.-S. Fu and G.-H. Chen, Fault-free Hamiltonian cycles in crossed cubes with conditional link faults, Inform. Sci. 177 (2007) 5664–5674. Crossref, Web of Science, Google Scholar
17. S. Latifi, M. Hegde and M. Naraghi-Pour, Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput. 43 (1994) 218–222. Crossref, Web of Science, Google Scholar
18. S. Latifi, S. Q. Zheng and N. Bagherzadeh, Optimal ring embedding in hypercubes with faulty links, Proc. IEEE Symposium on Fault-Tolerant Computing (1992) pp. 178–184. Crossref, Google Scholar
19. T. K. Li, C. H. Tsai, Jimmy J. M. Tan and L. H. Hsu, Bipanconnected and edge-fault-tolerant bipancyclic of hypercubes, Inform. Process. Lett. 87 (2003) 107–110. Crossref, Web of Science, Google Scholar
20. J. Li, Y. X. Yang and X. H. Gao, Hamiltonicity of the torus network under the conditional fault model, Int. J. Foundations of Computer Science 28 (2017) 211–227. Link, Web of Science, Google Scholar
21. H. Liu, X. Hu and S. Gao, The $g$ -good neighbor conditional diagnosability of twisted hypercubes under the PMC and MM* model, Appl. Math. Comput. 332 (2018) 484–492. Web of Science, Google Scholar
22. J.-J. Liu and Y.-L. Wang, Hamiltonian cycles in hypercubes with faulty edges, Inform. Sci. 256 (2014) 225–233. Crossref, Web of Science, Google Scholar
23. X.-W. Qin and R.-X. Hao, Conditional edge-fault-tolerant Hamiltonicity of the data center network, Discr. Appl. Math. 247 (2018) 165–179. Crossref, Web of Science, Google Scholar
24. C. H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theor. Comput. Sci. 314 (2004) 431–443. Crossref, Web of Science, Google Scholar
25. P.-Y. Tsai, J.-S. Fu and G.-H. Chen, Embedding Hamiltonian cycles in alternating group graphs under conditional fault model, Inform. Sci. 179 (2009) 851–857. Crossref, Web of Science, Google Scholar
26. C. H. Tsai, J. M. Tan, T. Liang and L. H. Hsu, Fault-tolerant Hamiltonian laceability of hypercubes, Inform. Process. Lett. 83 (2002) 301–306. Crossref, Web of Science, Google Scholar
27. Y. C. Tseng, Embedding a ring in a hypercube with both faulty links and faulty nodes, Inform. Process. Lett. 59 (1996) 217–222. Crossref, Web of Science, Google Scholar
28. S. Wang and S. Lin, Sufficient conditions for a graph to be super restricted edge-connected, Networks 51 (2008) 200–209. Crossref, Web of Science, Google Scholar
29. S. Wang, Z. Wang and M. Wang, The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks, Discr. Appl. Math. 217 (2017) 691–706. Crossref, Web of Science, Google Scholar
30. S. Wang and S. Zhang, Embedding hamiltonian paths in $k$ -ary $n$ -cubes with conditional edge faults, Theor. Comput. Sci. 412 (2011) 6570–6584. Crossref, Web of Science, Google Scholar
31. F. Wang and H. Zhang, Hamiltonian laceability in hypercubes with faulty edges, Discr. Appl. Math. 236 (2018) 438–445. Crossref, Web of Science, Google Scholar
32. M.-C. Yang, Cycle embedding in star graphs with conditional edge faults, Appl. Math. Comput. 215 (2010) 3541–3546. Web of Science, Google Scholar