×
Park, Jung-Heum; Lim, Hyeong-Seok; Kim, Hee-Chul

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

Theor. Comput. Sci. 377, No. 1-3, 170-180 (2007).
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\).

Cited in 1 Review
Cited in 49 Documents

MSC:

68R10 Graph theory (including graph drawing) in computer science

Keywords:

embedding; panconnected; pancyclic; edge-pancyclic; fault-hamiltonicity; fault tolerance; restricted HL-graphs; interconnection networks
Cite Review PDF
Full Text: DOI

References:

[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; 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; 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, (Bakker, J.; Nijman, A.; Treleaven, P., PARLE: Parallel Architectures and Languages Europe. PARLE: Parallel Architectures and Languages Europe, Parallel Architectures, vol. I (1987), Springer), 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; 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; 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; 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; 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. 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.