Structure connectivity and substructure connectivity of \(k\)-ary \(n\)-cube networks. (English) Zbl 1436.68051
Summary: The \(k\)-ary \(n\)-cube is one of the most attractive interconnection networks for parallel and distributed computing system. In this paper, we investigate the fault-tolerant capabilities of \(k\)-ary \(n\)-cubes with respect to the structure connectivity and substructure connectivity. Let \(H\) is a connected graph. The structure connectivity of a graph \(G\), denoted by \(\kappa (G; H)\), is the minimum cardinality of a set of connected subgraphs in \(G\), whose deletion disconnects the graph \(G\) and every element in the set is isomorphic to \(H\). The substructure connectivity of a graph \(G\), denoted by \(\kappa^s (G; H)\), is the minimum cardinality of a set of connected subgraphs in \(G\), whose deletion disconnects the graph \(G\) and every element in the set is isomorphic to a connected subgraph of \(H\). We show \(\kappa(Q_n^k; H)\) and \(\kappa^s(Q_n^k; H)\) for each \(H \in \{K_1, K_{1, 1}, K_{1, 2}, K_{1, 3} \}\).
MSC:
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
| 05C40 | Connectivity |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Anderson, E.; Brooks, J.; Grassl, C.; Scott, S., Performance of the CRAY T3E multiprocessor, Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, Association for Computing Machinery, New York, USA, San Jose, CA, United States, 1-17 (1997) |
| [2] | Ashir, Y. A.; Stewart, I. A., On embedding cycles in \(k\)-ary \(n\)-cubes, Parrallel Process. Lett., 7, 49-55 (1997) |
| [3] | Bettayeb, S., On the \(k\)-ary hypercube, Theor. Comput. Sci., 140, 333-339 (1995) · Zbl 0873.68013 |
| [4] | Borkar, S.; et al., iWarp: an integrated solution to high-speed parallel computing, Proc Supercomputing 88, 330-339 (1988), Publ by IEEE, New York, USA: Publ by IEEE, New York, USA Orlando, FL, USA |
| [5] | Bose, B.; Broeg, B.; Kwon, Y.; Ashir, Y., Lee distance and topological properties of \(k\)-ary \(n\)-cubes, IEEE Trans. Comput., 44, 8, 1021-1030 (1995) · Zbl 1054.68510 |
| [6] | Day, K., The conditional node connectivity of the \(k\)-ary \(n\)-cube, J. Interconnect. Netw., 5, 1, 13-26 (2004) |
| [7] | Day, K.; Al-Ayyoub, A. E., Fault diameter of \(k\)-ary \(n\)-cube networks, IEEE Trans. Parallel Distrib. Syst., 8, 9, 903-907 (1997) |
| [8] | Dong, Q., Embedding paths and cycles in 3-ary \(n\)-cubes with faulty nodes and links, Inf. Sci., 180, 1, 198-208 (2010) · Zbl 1183.68089 |
| [9] | Esfahanian, A.-H., Generalized measures of fault tolerance with application to \(n\)-cube networks, IEEE Trans. Comput., 38, 11, 1586-1591 (1989) |
| [10] | Fang, J.-F., The bipancycle-connectivity and the \(m\)-pancycle-connectivity of the \(k\)-ary \(n\)-cube, Comput. J., 53, 6, 667-678 (2010) |
| [11] | Harary, F., Conditional connecticity, Networks, 13, 3, 347-357 (1983) · Zbl 0514.05038 |
| [12] | Hsieh, S.-Y.; Chang, Y.-H., Extraconnectivity of \(k\)-ary \(n\)-cube networks, Theor. Comput. Sci., 443, 63-69 (2012) · Zbl 1246.68172 |
| [13] | Hsieh, S.-Y.; Kao, C.-Y., The conditional diagnosability of \(k\)-ary \(n\)-cubes under the comparison diagnosis model, IEEE Trans. Comput., 62, 4, 839-843 (2013) · Zbl 1365.68085 |
| [14] | Hsieh, S.-Y.; Lin, T.-J., Panconnectivity and edge-pancyclicity of \(k\)-ary \(n\)-cubes, Networks, 54, 1, 1-11 (2009) · Zbl 1205.05126 |
| [15] | Hsu, D. F., On container width and length in graphs, groups, and networks, IEICE Trans. Fundam. Electron.Commun. Comput. Sci., E77-A, 4, 668-680 (1994) |
| [16] | Hsu, L.-H.; Lin, C.-K., Graph Theory and Interconnection Networks (2008), CRC Press: CRC Press Boca Raton,FL, USA |
| [17] | Kessler, R. E.; Schwarzmeier, J. L., Cray T3D: a new dimension for Cray research, 38th Annual IEEE Computer Society International Computer Conference - COMPCON SPRING ’93, 176-182 (1993), Publ by IEEE, Piscataway, NJ, United States: Publ by IEEE, Piscataway, NJ, United States San Francisco, CA, USA |
| [18] | Latifi, S.; Hegde, M.; Naraghi-Pour, M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 43, 2, 218-222 (1994) |
| [19] | Lin, C.-K.; Zhang, L.; Wang, D.; Fan, J., Structure connectivity and substructure connectivity of hypercubes, Theor. Comput. Sci., 634, 97-107 (2016) · Zbl 1339.68208 |
| [20] | Noakes, M. D.; Wallach, D. A.; Dally, W. J., The \(J\)-machine multicomputer: an architectural evaluation, Comput. Archit. News, 21, 2, 224-235 (1993) |
| [21] | Shih, Y.-K.; Kao, S.-S., One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes, Theor. Comput. Sci., 412, 35, 4513-4530 (2011) · Zbl 1223.68086 |
| [22] | Stewart, I. A.; Xiang, Y., Embedding long paths in \(k\)-ary \(n\)-cubes with faulty nodes and links, IEEE Trans. Parallel Distrib. Syst., 19, 8, 1071-1085 (2008) |
| [23] | Stewart, I. A.; Xiang, Y., Bipanconnectivity and bipancyclicity in \(k\)-ary \(n\)-cubes, IEEE Trans. Parallel Distrib. Syst., 20, 1, 25-33 (2009) |
| [24] | Wang, S.; Feng, K.; Zhang, G., Strong matching preclusion for \(k\)-ary \(n\)-cubes, Discrete Appl. Math., 161, 18, 3054-3062 (2013) · Zbl 1287.05122 |
| [25] | Wang, S.; Zhang, G.; Feng, K., Fault tolerance in \(k\)-ary \(n\)-cube networks, Theor. Comput. Sci., 460, 34-41 (2012) · Zbl 1252.68044 |
| [26] | Wang, S.; Zhang, S.; Yang, Y., Hamiltonian path embeddings in conditional faulty \(k\)-ary \(n\)-cubes, Inf. Sci., 268, 463-488 (2014) · Zbl 1341.68139 |
| [27] | Xiang, Y.; Stewart, I. A., Bipancyclicity in \(k\)-ary \(n\)-cubes with faulty edges under a conditional fault assumption, IEEE Trans. Parallel Distrib. Syst., 22, 9, 1506-1513 (2011) |
| [28] | Yang, M.-C.; Tan, J. J.; Hsu, L.-H., Hamiltonian circuit and linear array embeddings in faulty \(k\)-ary \(n\)-cubes, J. Parallel Distrib. Comput., 67, 4, 362-368 (2007) · Zbl 1115.68032 |
| [29] | Yang, W.; Meng, J., Extraconnectivity of hypercubes, Appl. Math. Lett., 22, 6, 887-891 (2009) · Zbl 1200.05123 |
| [30] | Yang, Y.; Wang, S.; Li, J., Conditional connectivity of recursive interconnection networks respect to embedding restriction, Inf. Sci., 279, 273-279 (2014) · Zbl 1354.68019 |
| [31] | Yu, X.; Huang, X.; Zhang, Z., A kind of conditional connectivity of Cayley graphs generated by unicyclic graphs, Inf. Sci., 243, 86-94 (2013) · Zbl 1337.68214 |
| [32] | Zhang, S.; Wang, S., Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes, Theor. Comput. Sci., 491, 103-118 (2013) · Zbl 1277.68040 |
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.
