Embedded connectivity of ternary \(n\)-cubes. (English) Zbl 1482.05321
Summary: Let \(G_n\) be an \(n\)-dimensional recursive network. A set \(\mathcal{F}\subset V(G_n)\) (resp. \(\mathcal{F}\subset E( G_n))\) is called a \(t\)-embedded vertex cut (resp. \(t\)-embedded edge cut) of \(G_n\) if \(G_n-\mathcal{F}\) is disconnected and each vertex of which lies in a \(t\)-dimensional subnetwork of \(G_n-\mathcal{F}\). The \(t\)-embedded vertex connectivity \(\zeta_t( G_n)\) (resp. \(t\)-embedded edge connectivity \(\eta_t(G_n))\) of \(G_n\) is the minimum cardinality over all \(t\)-embedded vertex cuts (resp. \(t\)-embedded edge cuts) in \(G_n\), if any. In this paper, we prove that \(\zeta_t(Q_n^3)=2(n-t)3^t\) for \(0\leq t\leq n-2\), and \(\eta_t(Q_n^3)=2(n-t)3^t\) for \(0\leq t\leq n-1\), where \(Q_n^3\) is the ternary \(n\)-cube.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C40 | Connectivity |
| 68M10 | Network design and communication in computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
interconnection network; ternary \(n\)-cubes; fault tolerance; connectivity; embedded connectivityReferences:
| [1] | Adiga, N. R.; Blumrich, M. A.; Chen, D., Blue Gene/L torus interconnection network, IBM J. Res. Dev., 49, 2, 265-276 (2005) |
| [2] | Boesch, F.; Tindell, R., Circulants and their connectivities, J. Graph Theory, 8, 487-499 (1984) · Zbl 0549.05048 |
| [3] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001 |
| [4] | Bose, B.; Broeg, B.; Kwon, Y., Lee distance and topological properties of k-ary n-cubes, IEEE Trans. Comput., 44, 8, 1021-1030 (1995) · Zbl 1054.68510 |
| [5] | Chen, D.; Eisley, N.; Heidelberger, P., The IBM Blue Gene/Q interconnection fabric, IEEE MICRO, 32, 1, 32-43 (2012) |
| [6] | Costa, P.; Zahn, T.; Rowstron, A., Why should we integrate services, servers, and networking in a data center?, (Proceedings of the 1st ACM Workshop on Research on Enterprise Networking. Proceedings of the 1st ACM Workshop on Research on Enterprise Networking, New York, USA (2009)), 111-118 |
| [7] | Day, K.; Ai-Ayyoub, A. E., Fault diameter of k-ary n-cube networks, IEEE Trans. Parallel Distrib. Syst., 8, 903-907 (1997) |
| [8] | Ghozati, S. A.; Wasserman, H. C., The k-ary n-cube network: modeling, topological properties and routing strategies, Comput. Electr. Eng., 25, 3, 155-168 (1999) |
| [9] | Harary, F., Conditional connectivity, Networks, 13, 347-357 (1983) · Zbl 0514.05038 |
| [10] | Hsieh, S.-Y.; Chang, Y.-H., Extraconnectivity of k-ary n-cube networks, Theor. Comput. Sci., 443, 63-69 (2012) · Zbl 1246.68172 |
| [11] | Latifi, S.; Hegde, M.; Naraghi-Pour, M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 43, 2, 218-222 (1994) |
| [12] | Li, X.-J.; Xu, J.-M., Generalized measures for fault tolerance of star networks, Networks, 63, 3, 225-230 (2014) · Zbl 1387.05131 |
| [13] | Li, X.-J.; Dong, Q.-Q.; Yan, Z.; Xu, J.-M., Embedded connectivity of recursive networks, Theor. Comput. Sci., 653, 79-86 (2016) · Zbl 1353.68012 |
| [14] | Li, X.-J.; Zeng, X.-Q.; Xu, J.-M., Generalized measures of fault tolerance for bubble-sort networks, Appl. Math. Comput., 363, Article 124630 pp. (2019) · Zbl 1433.05176 |
| [15] | Mader, W., Minimale n-fach kantenzusammenhängende Graphen, Math. Ann., 191, 21-28 (1971) · Zbl 0198.29202 |
| [16] | Yang, Y.; Wang, S., Conditional connectivity of star graph networks under embedded restriction, Inf. Sci., 199, 15, 187-192 (2012) · Zbl 1248.68103 |
| [17] | 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 |
| [18] | 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 |
| [19] | Yuan, J.; Liu, A.; Ma, X., The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM* model, IEEE Trans. Parallel Distrib. Syst., 26, 4, 1165-1177 (2015) |
| [20] | Yuan, J.; Liu, A.; Qin, X., g-Good-neighbor conditional diagnosability measures for 3-ary n-cube networks, Theor. Comput. Sci., 626, 144-162 (2016) · Zbl 1336.68018 |
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.
