×

Note on reliability evaluation of arrangement graphs. (English) Zbl 1510.05155

Summary: The \(R^h\)-restricted connectivity \(\kappa^h\) is a significant measurement to estimate the reliability of large-scale processor system. The arrangement graph \(A_{n,k}\) is a generalization and also a competitive alternative of the star graph \(S_n\). In this paper, for any non-negative integer \(h\leq n-2\), we determine that \(\kappa^h(A_{n,2})=n(n-2)/2\) provided \(h\) is odd with \(h=n-3\), otherwise \(\kappa^h(A_{n,2})=(h+2)(n-2)-\lfloor h^2/2+h\rfloor\). This result implies the upper bound of \(\kappa^h(A_{n,k})\) given by L. P. Li et al. [Int. J. Heat Mass Transfer 51, No. 13–14, 3669–3682 (2008; Zbl 1148.80327)] is not optimal in a sense.

MSC:

05C40 Connectivity

Citations:

Zbl 1148.80327
Full Text: DOI

References:

[1] Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026
[2] Chiang, W.-K.; Chen, R. J., On the arrangement graph, Inf. Process. Lett., 66, 4, 215-219 (1998) · Zbl 1078.68674
[3] Cheng, E.; Lipták, L.; Qiu, K.; Shen, Z., A unified approach to the conditional diagnosability of interconnection networks, J. Interconnect. Netw., 13, 1250007 (2012)
[4] Cheng, E.; Lipták, L.; Yuan, A., Linearly many faults in arrangement graphs, Networks, 61, 4, 281-289 (2013) · Zbl 1269.68028
[5] Cheng, E.; Qiu, K.; Shen, Z., On the restricted connectivity of the arrangement graph, J. Supercomput., 73, 8, 3669-3682 (2017)
[6] Day, K.; Tripathi, A., Arrangement graphs: a class of generalized star graphs, Inf. Process. Lett., 42, 5, 235-241 (1992) · Zbl 0772.68005
[7] Day, K.; Tripathi, A., Embedding of cycles in arrangement graphs, IEEE Trans. Comput., 42, 8, 1002-1006 (1993) · Zbl 1395.05090
[8] Esfahanian, A. H., Generalized measures of fault tolerance with application to \(n\)-cube networks, IEEE Trans. Comput., 38, 11, 1586-1591 (1989)
[9] Harary, F., Conditional connectivity, Networks, 13, 347-357 (1983) · Zbl 0514.05038
[10] Hsieh, S. Y.; Chen, G. H.; Ho, C. W., Fault-free hamiltonian cycles in faulty arrangement graphs, IEEE Trans. Parallel. Distrib. Syst., 10, 3, 223-237 (1999)
[11] Latifi, S.; Hegde, M.; Naraghi, P. M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 43, 2, 218-222 (1994)
[12] Lei, Y.; Meng, J., Structure fault-tolerance of arrangement graphs, Appl. Math. Comput., 381, 15, 125287 (2020) · Zbl 1508.05092
[13] Li, P.; Xu, M., The super spanning connectivity of arrangement graphs, Int. J. Found. Comput. Sci., 28, 8, 1047-1072 (2017) · Zbl 1390.05114
[14] Li, X.-J.; Xu, J. M., Generalized measures of fault tolerance in exchanged hypercubes, Inf. Process. Lett., 113, 14-16, 533-537 (2013) · Zbl 1284.68082
[15] Li, X.-J.; Xu, J. M., Generalized measures for fault tolerance of star networks, Networks, 63, 3, 225-230 (2014) · Zbl 1387.05131
[16] Lin, L.; Zhou, S., Conditional connectivity for \(( n , k )\)-arrangement graphs, J. Math. Study, 45, 4, 350-364 (2012) · Zbl 1289.05248
[17] Oh, A. D.; Choi, H., Generalized measures of fault tolerance in \(n\)-cube networks, IEEE Trans. Parallel. Distrib. Syst., 4, 702-703 (1993)
[18] Wang, S.; Feng, K., Fault tolerance in the arrangement graphs, Theor. Comput. Sci., 533, 64-71 (2014) · Zbl 1358.68046
[19] Wan, M.; Zhang, Z., A kind of conditional vertex connectivity of star graphs, Appl. Math. Lett., 22, 264-267 (2009) · Zbl 1163.05323
[20] Xu, J. M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht/Boston/London · Zbl 1046.68026
[21] Zhou, S.; Xu, J. M., Conditional fault tolerance of arrangement graphs, Inf. Process. Lett., 111, 21, 1037-1043 (2011) · Zbl 1260.68309
[22] Zhou, S.; Xu, J. M., Fault diagnosability of arrangement graphs, Inf. Sci., 246, 177-190 (2013) · Zbl 1337.68215
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.