Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements. (English) Zbl 1115.68116

Summary: We deal with the graph \(G_0 \oplus G_1\) obtained from merging two graphs \(G_0\) and \(G_1\) with n vertices each by \(n\) pairwise nonadjacent edges joining vertices in \(G_0\) and vertices in \(G_1\). The main problems studied are how fault-panconnectivity and fault-pancyclicity of \(G_0\) and \(G_1\) are translated into fault-panconnectivity and fault-pancyclicity of \(G_0 \oplus G_1\), respectively. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of \(G_0 \oplus G_1\) connecting two lower dimensional networks \(G_0\) and \(G_1\). Applying our results to a class of hypercube-like interconnection networks called restricted HL-graphs, we show that in a restricted HL-graph \(G\) of degree \(m (\geq 3)\), each pair of vertices are joined by a path in \(G\backslash F\) of every length from \(2m-3\) to \(|V(G\backslash F)|-1\) for any set \(F\) of faulty elements (vertices and/or edges) with \(|F|\leq m-3\), and there exists a cycle of every length from 4 to \(|V(G\backslash F)|\) for any fault set \(F\) with \(|F|\leq m-2\).


68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Araki, T., Edge-pancyclicity of recursive circulants, Inform. proc. lett., 88, 287-292, (2003) · Zbl 1178.68022
[2] Araki, T.; Shibata, Y., Pancyclicity of recursive circulant graphs, Inform. proc. lett., 81, 187-190, (2002) · Zbl 1013.68137
[3] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), American Elsevier · Zbl 1134.05001
[4] Chang, J.-M.; Yang, J.-S.; Wang, Y.-L.; Cheng, Y., Panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs, Networks, 44, 302-310, (2004) · Zbl 1055.05076
[5] Chedid, F.B., On the generalized twisted cube, Inform. proc. lett., 55, 49-52, (1995) · Zbl 0875.68142
[6] P. Cull, S. Larson, The Möbius cubes, in: Proc. of the 6th IEEE Distributed Memory Computing Conf., 1991, pp. 699-702
[7] Efe, K., A variation on the hypercube with lower diameter, IEEE trans. comput., 40, 11, 1312-1316, (1991)
[8] Efe, K., The crossed cube architecture for parallel computation, IEEE trans. parallel distributed syst., 3, 5, 513-524, (1992)
[9] Esfahanian, A.-H.; Ni, L.M.; Sagan, B.E., The twisted \(n\)-cube with application to multiprocessing, IEEE trans. comput., 40, 1, 88-93, (1991) · Zbl 1395.05139
[10] Fan, J., Hamilton-connectivity and cycle-embedding of the Möbius cubes, Inform. proc. lett., 82, 113-117, (2002) · Zbl 1013.68008
[11] J. Fan, X. Lin, X. Jia, R.W.H. Lau, Edge-pancyclicity of twisted cubes, in: Proc. of International Symposium on Algorithms and Computation ISAAC 2005, December 2005, pp. 1090-1099 · Zbl 1175.68291
[12] Fan, J.; Lin, X.; Jia, X., Node-pancyclicity and edge-pancyclicity of crossed cubes, Inform. proc. lett., 93, 133-138, (2005) · Zbl 1169.05339
[13] Hilbers, P.A.J.; Koopman, M.R.J.; van de Snepscheut, J.L.A., The twisted cube, (), 152-159
[14] S.-Y. Hsieh, N.-W. Chang, Cycle embedding on the Möbius cube with both faulty nodes and faulty edges, in: Proc. of 11th International Conference on Parallel and Distributed Systems ICPADS 2005, 2005
[15] Latifi, S.; Bagherzadeh, N.; Gajjala, R.R., Fault-tolerant embedding of linear arrays and rings in the star graph, Comput. elect. eng., 23, 2, 95-107, (1997)
[16] Li, T., Cycle embedding in star graphs with edge faults, Appl. math. comput., 167, 891-900, (2005) · Zbl 1075.05047
[17] Ma, M.; Xu, J.-M., Panconnectivity of locally twisted cubes, Appl. math. lett., 19, 673-677, (2006) · Zbl 1118.05050
[18] McSorley, J.P., Counting structures in the Möbius ladder, Discrete math., 184, 1-3, 137-164, (1998) · Zbl 0957.05057
[19] Park, C.-D.; Chwa, K.Y., Hamiltonian properties on the class of hypercube-like networks, Inform. proc. lett., 91, 11-17, (2004) · Zbl 1178.68043
[20] Park, J.-H., Cycle embedding of faulty recursive circulants, J. kiss, 31, 2, 86-94, (2004), (in Korean)
[21] Park, J.-H.; Chwa, K.Y., Recursive circulants and their embeddings among hypercubes, Theoret. comput. sci., 244, 35-62, (2000) · Zbl 0945.68003
[22] J.-H. Park, H.-C. Kim, H.-S. Lim, Fault-hamiltonicity of hypercube-like interconnection networks, in: Proc. of IEEE International Parallel and Distributed Processing Symposium IPDPS 2005, Denver, Apr. 2005
[23] Park, J.-H.; Kim, H.-C.; Lim, H.-S., Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements, IEEE trans. parallel distributed syst., 17, 3, 227-240, (2006)
[24] Sengupta, A., On ring embedding in hypercubes with faulty nodes and links, Inform. proc. lett., 68, 207-214, (1998) · Zbl 1339.68213
[25] N.K. Singhvi, K. Ghose, The Mcube: A symmetrical cube based network with twisted links, in: Proc. of the 9th IEEE Int. Parallel Processing Symposium IPPS 1995, 1995, pp. 11-16
[26] A.S. Vaidya, P.S.N. Rao, S.R. Shankar, A class of hypercube-like networks, in: Proc. of the 5th IEEE Symposium on Parallel and Distributed Processing SPDP 1993, December 1993, pp. 800-803
[27] Yang, X.; Evans, D.J.; Megson, G.M., The locally twisted cubes, Int. J. comput. math., 82, 4, 401-413, (2005) · Zbl 1097.68522
[28] Yang, M.-C.; Li, T.-K.; Tan, J.J.M.; Hsu, L.-H., Fault-tolerant cycle-embedding of crossed cubes, Inform. proc. lett., 88, 149-154, (2003) · Zbl 1178.68092
[29] Yang, M.-C.; Li, T.-K.; Tan, J.J.M.; Hsu, L.-H., On embedding cycles into faulty twisted cubes, Inform. sci., 176, 676-690, (2006) · Zbl 1103.68028
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.