Edge-bipancyclicity in conditional edge-faulty $k$-ary $n$-cubes

Wang, Shiying; Zhang, Shurong

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 3-4, pp. 85-113

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

The class of $k$-ary $n$-cubes represents the most commonly used interconnection topology for parallel and distributed computing systems. In this paper, we consider the faulty $k$-ary $n$-cube with even $k\ge 4$ and $n\ge 2$ such that each vertex of the $k$-ary $n$-cube is incident with at least two healthy edges. Based on this requirement, we investigate the fault-tolerant capabilities of the $k$-ary $n$-cube with respect to the edge-bipancyclicity. We prove that in the $k$-ary $n$-cube ${𝒬}_n^k$, every healthy edge is contained in fault-free cycles of even lengths from $6$ to $\left|V\right({𝒬}_n^k\left)\right|$, even if the ${𝒬}_n^k$ has up to $4n-5$ edge faults and our result is optimal with respect to the number of edge faults tolerated.

Classification : 05C38
Keywords: Interconnection network, fault-tolerant, $k$-ary $n$-cube, conditional edge-fault, edge-bipancyclicity

[1] N.R. Adiga, M.A. Blumrich, D. Chen, P. Coteus, A. Gara, M. Giampapa, P. Heidelberger, S. Singh, B.D. Steinmacher-Burow, T. Takken, M. Tsao, P. Vranas, Blue Gene/L torus interconnection network. IBM J. Res. Dev. 49 (2005) 265–276. | DOI

[2] Y.A. Ashir, I.A. Stewart, On embedding cycles in k-ary n-cubes. Paral. Process. Lett. 7 (1997) 49–55. | MR | DOI

[3] Y.A. Ashir, I.A. Stewart, Fault-tolerant embeddings of hamiltonian circuits in k-ary n-cubes. SIAM J. Discr. Math. 15 (2002) 317–328. | MR | Zbl | DOI

[4] J.A. Bondy, U.S.R. Murty, Graph Theory. Springer, New York (2007). | MR | Zbl

[5] B. Bose, B. Broeg, Y. Kwon, Y. Ashir, Lee distance and topological properties of k-ary n-cubes. IEEE Trans. Comput. 44 (1995) 1021–1030. | MR | Zbl | DOI

[6] K. Day, A.-E. Al-Ayyoub, Fault diameter of k-ary n-cube networks. IEEE Trans. Paral. Distrib. Syst. 8 (1997) 903–907. | DOI

[7] S.-Y. Hsieh, T.-H. Shen, Edge-bipancyclicity of a hypercube with faulty vertices and edges. Discr. Appl. Math. 156 (2008) 1802–1808. | MR | Zbl | DOI

[8] R.E. Kessler, J.L. Schwarzmeier, Cray T3D: a new dimension for cray research. Proceedings of 38th IEEE Computer Society International Conference, IEEE Press (1993) 176–182.

[9] H.-C. Kim, J.-H. Park, Fault hamiltonicity of two-dimensional torus networks, Proceedings of Workshop on Algorithms and Computation WAAC’00, Tokyo, Japan (2000) 110–117.

[10] C.-N. Kuo, S.-Y. Hsieh, Pancyclicity and bipancyclicity of conditional faulty folded hypercubes. Inf. Sci. 180 (2010) 2904–2914. | MR | Zbl | DOI

[11] J. Li, S. Wang, D. Liu, Pancyclicity of ternary n-cube networks under the conditional fault model. Inf. Process. Lett. 111 (2011) 370–374. | MR | Zbl | DOI

[12] J. Li, S. Wang, D. Liu, S. Lin, Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges. Inf. Sci. 181 (2011) 2260–2267. | MR | Zbl | DOI

[13] C. Peterson, J. Sutton, P. Wiley, iWarp: A 100-MOPS LIW microprocessor for multicomputers. IEEE Micro 11 (1991) 26–37. | DOI

[14] I.A. Stewart, Y. Xiang, Embedding long paths in k-ary n-cubes with faulty nodes and links. IEEE Trans. Paral. Distrib. Syst. 19 (2008) 1071–1085. | DOI

[15] C.-H. Tsai, Y.-C. Lai, Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes. Inf. Sci. 177 (2007) 5590–5597. | MR | Zbl | DOI

[16] S. Wang, S. Lin, Path embeddings in faulty 3-ary n-cubes. Inf. Sci. 180 (2010) 191–197. | MR | Zbl | DOI

[17] S. Wang, S. Zhang, Embedding hamiltonian paths in k-ary n-cubes with conditional edge faults. Theor. Comput. Sci. 412 (2011) 6570–6584. | MR | Zbl | DOI

[18] Y. Xiang, I.A. Stewart, Bipancyclicity in k-ary n-cubes with faulty edges under a conditional fault assumption. IEEE Trans. Parallel Distrib. Syst. 22 (2011) 1506–1513. | DOI