Document Zbl 1338.68037

Conditional fault-tolerant edge-bipancyclicity of hypercubes with faulty vertices and edges. (English) Zbl 1338.68037

Theor. Comput. Sci. 627, 82-89 (2016).

Summary: Let \(F\) be a faulty set in an \(n\)-dimensional hypercube \(Q_n\) such that in \(Q_n - F\) each vertex is incident to at least two edges, and let \(f_v\), \(f_e\) be the numbers of faulty vertices and faulty edges in \(F\), respectively. In this paper, we consider the fault-tolerant edge-bipancyclicity of hypercubes. It is shown that each edge in \(Q_n - F\) for \(n \geq 3\) lies on a fault-free cycle of any even length from 6 to \(2^n - 2 f_v\) if \(f_v + f_e \leq 2 n - 5\). This gives an answer for a problem proposed by the first author et al. [“Fault-tolerant edge-bipancyclicity of faulty hypercubes under the conditional-fault model”, Inf. Sci. 329, 317–328 (2016; doi:10.1016/j.ins.2015.09.029)].

Cited in 1 Document

MSC:

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

Keywords:

cycle embedding; interconnection network; fault-tolerance; hypercubes; edge-bipancyclicity

Cite Review PDF

Full Text: DOI

References:

[1]	Akl, S. G., Parallel Computation: Models and Methods (1997), Prentice Hall
[2]	Chang, N.-W.; Hsieh, S.-Y., Fault-tolerant bipancyclicity of faulty hypercubes under the generalized conditional-fault model, IEEE Trans. Commun., 59, 3400-3409 (2011)
[3]	Cheng, C.-W.; Hsieh, S.-Y., Fault-tolerant cycle embedding in cartesian product graphs: edge-pancyclicity and edge-bipancyclicity with faulty edges, IEEE Trans. Parallel Distrib. Syst., 26, 2997-3010 (2015)
[4]	Cheng, D. Q.; Guo, D. C., Fault-tolerant cycle embedding in the faulty hypercubes, Inform. Sci., 253, 157-162 (2013) · Zbl 1337.68202
[5]	Cheng, D. Q.; Hao, R.-X.; Feng, Y.-Q., Conditional edge-fault pancyclicity of augmented cubes, Theoret. Comput. Sci., 510, 94-101 (2013) · Zbl 1408.05120
[6]	Fu, J.-S., Vertex-pancyclicity of twisted cubes with maximal faulty edges, Inter. J. Comput. Math., 89, 728-740 (2012) · Zbl 1257.05105
[7]	Fu, J.-S., Fault-tolerant cycle embedding in the hypercube, Parallel Comput., 29, 821-832 (2003) · Zbl 1243.68030
[8]	Gu, M.-M.; Hao, R.-X.; Feng, Y.-Q., Fault-tolerant cycle embedding in balanced hypercubes with faulty vertices and faulty edges, J. Interconnect. Networks, 15, 1550002, 1-16 (2015)
[9]	Hao, R. X.; Zhang, R.; Feng, Y.-Q.; Zhou, J.-X., Hamiltonian cycle embedding for fault tolerance in balanced hypercubes, Appl. Math. Comput., 244, 447-456 (2014) · Zbl 1335.05104
[10]	Hsieh, S.-Y., Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges, Parallel Comput., 32, 84-91 (2005)
[11]	Hsieh, S.-Y.; Shen, T.-H., Edge-bipancyclicity of a hypercube with faulty vertices and edges, Discrete Appl. Math., 156, 1802-1808 (2008) · Zbl 1152.05338
[12]	Kuo, C.-N., Every edge lies on cycles embedding in folded hypercubes with vertex-fault-tolerant, Theoret. Comput. Sci., 589, 47-52 (2015) · Zbl 1319.68030
[13]	Kuo, C.-N., Pancyclicity and bipancyclicity of folded hypercubes with both vertex and edge faults, Theoret. Comput. Sci., 602, 125-131 (2015) · Zbl 1329.68050
[14]	Li, H. Z.; Yang, W. H.; Meng, J. X., Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, Discrete Math., 312, 3087-3095 (2012) · Zbl 1251.05077
[15]	Li, J.; Wang, S. Y.; Liu, D.; Lin, S. W., Edge-bipancyclicity of the \(k\)-ary \(n\)-cubes with faulty nodes and edges, Inform. Sci., 181, 2260-2267 (2011) · Zbl 1216.68057
[16]	Li, T. K.; Tsai, C. H.; Tan, J. J.M.; Hsu, L. H., Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes, Inform. Process. Lett., 87, 107-110 (2003) · Zbl 1161.68684
[17]	Ma, M. J.; Liu, G. Z.; Pan, X. F., Path embedding in faulty hypercubes, Appl. Math. Comput., 192, 233-238 (2007) · Zbl 1193.05099
[18]	Saad, Y.; Schultz, M. H., Topological properties of hypercubes, IEEE Trans. Comput., 37, 867-872 (1988)
[19]	Shih, L. M.; Tan, J. J.M.; Hsu, L. H., Edge-bipancyclicity of conditional faulty hypercubes, Inform. Process. Lett., 105, 20-25 (2007) · Zbl 1185.05091
[20]	Szepietowski, A., Hamiltonian cycles in hypercubes with \(2 n - 4\) faulty edges, Inform. Sci., 215, 75-82 (2012) · Zbl 1251.68171
[21]	Szepietowski, A., Fault tolerance of edge pancyclicity in alternating group graphs, Appl. Math. Comput., 218, 9875-9881 (2012) · Zbl 1245.05083
[22]	Tsai, C. H., Cycles embedding in hypercubes with node failures, Inform. Process. Lett., 102, 242-246 (2007) · Zbl 1184.68054
[23]	Tsai, C. H., Embedding various even cycles in a hypercube with node failures, (Proceedings of the 24th Workshop on Combinatorial Mathematics and Computation Theory (2007)), 229-234
[24]	Tsai, C. H., Fault-tolerant cycles embedded in hypercubes with mixed link and node failures, Appl. Math. Lett., 21, 855-860 (2008) · Zbl 1155.68017
[25]	Tsai, C. H.; Lai, Y. C., Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Inform. Sci., 177, 5590-5597 (2007) · Zbl 1132.68019
[26]	Ucar, B.; Aykanat, C.; Kaya, K.; Ikinci, M., Task assignment in heterogeneous computing systems, J. Parallel Distrib. Comput., 66, 32-46 (2006) · Zbl 1158.68351
[27]	Wang, H. L.; Wang, J. W.; Xu, J. M., Edge-fault-tolerance bipanconnectivity of hypercubes, Inform. Sci., 179, 404-409 (2009) · Zbl 1163.68314
[28]	Wang, S. Y.; Li, J.; Lin, S. W.; Wang, R. X., Fault-tolerant embedding of cycles of various lengths in \(k\)-ary \(n\)-cubes, Inform. and Comput., 230, 55-66 (2013) · Zbl 1339.68028
[29]	Wang, S. Y.; Feng, K.; Zhang, S. R.; Li, J., Embedding long cycles in faulty \(k\)-ary 2-cubes, Appl. Math. Comput., 218, 5409-5413 (2012) · Zbl 1238.68031
[30]	Xu, J. M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers · Zbl 1046.68026
[31]	Xu, J. M.; Du, Z. Z.; Xu, M., Edge-fault-tolerant edge-bipancyclicity of hypercubes, Inform. Process. Lett., 96, 146-150 (2005) · Zbl 1184.68117
[32]	Xu, J. M.; Ma, M. J., Survey on path and cycle embedding in some networks, Front. Math. China, 217-252 (2009) · Zbl 1176.90081
[33]	Yang, D.-W.; Feng, Y.-Q.; Kwak, J. H.; Zhou, J.-X., Fault-tolerant edge-bipancyclicity of faulty hypercubes under the conditional-fault model, Inform. Sci., 329, 317-328 (2016) · Zbl 1387.68042
[34]	Yang, W. H.; Li, H. Z.; He, W. H., Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees, Inter. J. Comput. Math., 92, 1345-1352 (2015) · Zbl 1317.05089

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.