×

The \(g\)-good-neighbor diagnosability of \((n,k)\)-star graphs. (English) Zbl 1355.68027

Summary: Many large-scale multiprocessor or multi-computer systems take interconnection networks as underlying topologies. Fault diagnosis is especially important to identify fault tolerability of such systems. The g-good-neighbor (conditional) diagnosability such that every fault-free node has at least \(g\) fault-free neighbors is a novel measure of diagnosability. In this paper, we show that the \(g\)-good-neighbor diagnosability of the \((n, k)\)-star graph \(S_{n, k}\) under the PMC model (\(2 \leq k \leq n - 1\) and \(1 \leq g \leq n - k\)) and the comparison model (\(2 \leq k \leq n - 1\) and \(2 \leq g \leq n - k\)) is \(n + g(k - 1) - 1\), respectively. In addition, we derive that 1-good-neighbor diagnosability of \(S_{n, k}\) under the comparison model is \(n + k - 2\) for \(3 \leq k \leq n - 1\) and \(n \geq 4\). As a supplement, we also derive that the \(g\)-good-neighbor diagnosability of the \((n, 1)\)-star graph \(S_{n, 1}\) (\(1 \leq g \leq \lfloor n / 2 \rfloor - 1\) and \(n \geq 4\)) under the PMC model and the comparison model is \(\lceil n / 2 \rceil - 1\), respectively.

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chiang, W.-K.; Chen, R.-J., The \((n, k)\)-star graph: a generalized star graph, Inform. Process. Lett., 56, 5, 259-264 (1995) · Zbl 1027.68645
[2] Chang, G.-Y.; Chang, G.-J.; Chen, G.-H., Diagnosabilities of regular networks, IEEE Trans. Parallel Distrib. Syst., 16, 4, 314-323 (2005)
[3] Chang, N.-W.; Deng, W.-H.; Hsieh, S.-Y., Conditional diagnosability of \((n, k)\)-star networks under the comparison diagnosis model, IEEE Trans. Reliab., 64, 1, 132-143 (2015)
[4] Chang, N.-W.; Hsieh, S.-Y., Structural properties and conditional diagnosability of star graphs by using PMC model, IEEE Trans. Parallel Distrib. Syst., 25, 11, 3002-3011 (2014)
[5] Cheng, E.; Kelm, J.; Renzi, J., Strong matching preclusion of \((n, k)\)-star graph, Theoret. Comput. Sci., 615, 91-101 (2016) · Zbl 1334.05115
[6] Cheng, E.; Liták, L.; Qiu, K.; Shen, Z., On deriving conditional diagnosability of interconnection networks, Inform. Process. Lett., 112, 17-18, 674-677 (2012) · Zbl 1248.68105
[7] Cheng, E.; Qiu, K.; Shen, Z., A note on the alternating group network, J. Supercomput., 59, 1, 246-248 (2012)
[8] Cheng, E.; Qiu, K.; Shen, Z., Length two path centered surface areas of the \((n, k)\)-star graph, Inform. Sci., 332, 115-130 (2016) · Zbl 1390.68496
[9] Chiu, C.-W.; Huang, K.-S.; Yang, C.-B.; Tseng, C.-T., An adaptive heuristic algorithm with the probabilistic safety vector for fault-tolerant routing on the \((n, k)\)-star graph, Internat. J. Found. Comput. Sci., 25, 6, 723-743 (2014) · Zbl 1304.68018
[10] Fan, J., Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst., 13, 7, 687-692 (2002)
[11] Hao, R.-X.; Feng, Y.-Q.; Zhou, J.-X., Conditional diagnosability of alternating group graphs, IEEE Trans. Comput., 62, 4, 827-831 (2013) · Zbl 1365.05125
[12] Hao, R.-X.; Tian, Z.-X.; Xu, J.-M., Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs, Theoret. Comput. Sci., 627, 36-53 (2016) · Zbl 1338.68030
[13] Lai, P.-L.; Tan, J. J.-M.; Chang, C.-P.; Hsu, L.-H., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput., 54, 2, 165-175 (2005)
[14] Li, X.; Xu, J.-M., Fault-tolerance of \((n, k)\)-star networks, Appl. Math. Comput., 248, 525-530 (2014) · Zbl 1338.05255
[15] Lin, C.-K.; Tan, J. J.-M.; Hsu, L.-H.; Cheng, E.; Liták, L., Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model, J. Interconnect. Netw., 9, 1/2, 83-97 (2008)
[16] Lin, L.; Xu, L.; Zhou, S., Conditional diagnosability and strong diagnosability of shuffle-cubes under the comparison model, Int. J. Comput. Math., 92, 2, 230-249 (2015) · Zbl 1310.05206
[17] Lin, L.; Xu, L.; Zhou, S., Conditional diagnosability and strong diagnosability of split-star networks under the PMC model, Theoret. Comput. Sci., 562, 565-580 (2015) · Zbl 1303.68035
[18] Lin, L.; Zhou, S.; Xu, L.; Wang, D., Conditional diagnosability of arrangement graphs under the PMC model, Theoret. Comput. Sci., 548, 79-97 (2014) · Zbl 1408.68034
[19] Malek, M., A comparison connection assignment for diagnosis of multiprocessor systems, (Proceedings of 7th International Symposium on Computer Architecture (1980)), 31-35
[20] Maeng, J.; Malek, M., A comparison connection assignment for self-diagnosis of multiprocessor systems, (Proceedings of 11th International Fault-Tolerant Computing (1981)), 173-175
[21] Peng, S.-L.; Lin, C.-K.; Tan, J. J.-M.; Hsu, L.-H., The \(g\)-good-neighbor conditional diagnosability of hypercube under PMC model, Appl. Math. Comput., 218, 21, 10406-10412 (2012) · Zbl 1247.68032
[22] Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput., EC-16, 6, 848-854 (1967) · Zbl 0189.16904
[23] Sengupta, A.; Dahbura, A. T., On self-diagnosable multiprocessor systems: diagnosis by the comparison approach, IEEE Trans. Comput., 44, 11, 1386-1396 (1992) · Zbl 1395.68062
[24] Wang, M.; Lin, Y.; Wang, S., The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and \(M M^\ast\) model, Theoret. Comput. Sci., 628, 92-100 (2016) · Zbl 1338.68036
[25] Xu, M.; Hu, X.; Shang, S., The conditional diagnosability of shuffle-cubes, J. Syst. Sci. Complex., 23, 1, 81-90 (2010) · Zbl 1298.68053
[26] Yang, W.; Li, H.; Guo, X., A kind of conditional fault tolerance of \((n, k)\)-star graphs, Inform. Process. Lett., 110, 22, 1007-1011 (2010) · Zbl 1379.68262
[27] Yuan, J.; Liu, A.; Ma, X.; Liu, X.; Qin, X.; Zhang, J., 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)
[28] Yuan, J.; Liu, A.; Qin, X.; Zhang, J.; Li, J., \(g\)-good-neighbor conditional diagnosability measures for 3-ary \(n\)-cube networks, Theoret. Comput. Sci., 626, 144-162 (2016) · Zbl 1336.68018
[29] Zhou, S., The conditional fault diagnosability of \((n, k)\)-star graphs, Appl. Math. Comput., 218, 19, 9742-9749 (2012) · Zbl 1245.05122
[30] Zhou, S.; Xiao, W., Conditional diagnosability of alternating group networks, Inform. Process. Lett., 110, 10, 403-409 (2010) · Zbl 1229.68011
[31] Zhu, Q., On conditional diagnosability and reliability of the BC networks, J. Supercomput., 45, 2, 173-184 (2008)
[32] Zhu, Q.; Liu, S.-Y.; Xu, M., On conditional diagnosability of the folded hypercubes, Inform. Sci., 178, 4, 1069-1077 (2008) · Zbl 1134.68014
[33] Zhu, Q.; Wang, X.-K.; Cheng, G., Reliability evaluation of BC networks, IEEE Trans. Comput., 62, 11, 2337-2340 (2013) · Zbl 1365.68100
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.