Skip to main content
SpringerLink
Log in

The g-Good-Neighbor Conditional Diagnosability of Locally Twisted Cubes

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

Abstract

In the work of Peng et al. (Appl Math Comput 218(21):10406–10412, 2012), a new measure was proposed for fault diagnosis of systems: namely g-good-neighbor conditional diagnosability, which requires that any fault-free vertex has at least g fault-free neighbors in the system. In this paper, we establish the g-good-neighbor conditional diagnosability of locally twisted cubes under the PMC model and the MM\(^*\) model.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Preparata, F.P., Metze, G., Chien, R.T.: On the connection assignment problem of diagnosis systems. IEEE Trans. Electron. Comput. EC–16(6), 848–854 (1967)

    Article  MATH  Google Scholar 

  2. Maeng, J., Malek, M.: A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proceeding of 11th International Symposium on Fault-Tolerant Computing, 1981, pp. 173–175

  3. Sengupta, A., Dahbura, A.: On self-diagnosable multiprocessor system: diagnosis by the comparison approach. IEEE Trans. Comput. 41(11), 1386–1396 (1992)

    Article  MathSciNet  Google Scholar 

  4. Chang, G.Y., Chen, G.H., Chang, G.J.: \((t, k)\)-diagnosis for matching composition networks under the MM\(^*\) model. IEEE Trans. Comput. 56(1), 73–79 (2007)

    Article  MathSciNet  Google Scholar 

  5. Chen, C.A., Hsieh, S.Y.: \((t, k)\)-diagnosis for component-composition graphs under the MM\(^*\) model. IEEE Trans. Comput. 60(12), 1704–1717 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  6. 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)

    Article  Google Scholar 

  7. Chang, N.-W. , Lin, T.-Y., Hsieh, S.-Y.: Conditional diagnosability of \(k\)-ary \(n\)-cubes under the PMC model. ACM Trans. Des. Autom. Electron. Syst. (2012). doi:10.1145/2348839.2348850

  8. Hsieh, S.Y., Lee, C.W.: Diagnosability of two-matching composition networks under the MM\(^*\) model. IEEE Trans. Depend. Secure Comput. 8(2), 246–255 (2011)

    Article  Google Scholar 

  9. Xu, M., Thulasiraman, K., Hu, X.D.: Conditional diagnosability of matching composition networks under the PMC model, IEEE Trans. Circuits Syst., II, Express. Briefs 56(11), 875–879 (2009)

    Google Scholar 

  10. Zhu, Q., Liu, S.Y., Xu, M.: On conditional diagnosability of the folded hypercubes. Inf. Sci. 178(4), 1069–1077 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. 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)

    Article  Google Scholar 

  12. Hsu, G.H., Chiang, C.F., Shih, L.M., Hsu, L.H., Tan, J.J.M.: Conditional diagnosability of hypercubes under the comparison diagnosis model. J. Syst. Archit. 55(2), 140–146 (2009)

    Article  Google Scholar 

  13. Yang, M.C.: Conditional diagnosability of matching composition networks under the MM\(^*\) model. Inf. Sci. 233(1), 230–243 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  14. Zhou, S.: The conditional diagnosability of crossed cubes under the comparison model. Int. J. Comput. Math. 87(15), 3387–3396 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  15. Zhu, Q.: On conditional diagnosability and reliability of the BC networks. J. Supercomput. 45(2), 173–184 (2008)

    Article  Google Scholar 

  16. Peng, S.L., Lin, C.K., Tan, J.J.M., Hsu, L.H.: The \(g\)-good-neighbor conditional diagnosability of hypercube under the PMC model. Appl. Math. Comput. 218(21), 10406–10412 (2012)

    MathSciNet  MATH  Google Scholar 

  17. Wang, M., Liu, Y., Wang, S.: The \(2\)-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM\(^*\) model. Theor. Comput. Sci. 628, 92–100 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  18. Wang, M., Guo, Y., Wang, S.: The \(1\)-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM\(^*\) model. Int. J. Comput. Math. (2016). doi:10.1080/00207160.2015.1119817

    MATH  Google Scholar 

  19. Wang, S., Han, W.: The \(g\)-good-neighbor conditional diagnosability of \(n\)-dimensional hypercubes under the MM\(^*\) model. Inf. Process. Lett. 116, 574–577 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  20. Yuan, J., Liu, A.X., Ma, 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)

    Article  Google Scholar 

  21. Yuan, J., Liu, A., Qin, X., Zhang, J., Li, J.: \(g\)-good-neighbor conditional diagnosability measures for \(3\)-ary \(n\)-cube networks. Theor. Comput. Sci. 626, 144–162 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  22. Lin, L., Xu, L., Wang, D., Zhou, S.: The \(g\)-good-neighbor conditional diagnosability of arrangement graphs. IEEE Trans. Depend. Secure Comput. (2016). doi:10.1109/TDSC.2016.2593446

    Google Scholar 

  23. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. The Macmillan Press Ltd, New York (1976)

    Book  MATH  Google Scholar 

  24. Yang, X.F., Evans, D.J., Megson, G.M.: The locally twisted cubes. Int. J. Comput. Math. 82(4), 401–413 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  25. Yang, X.F., Megson, G.M., Evans, D.J.: Locally twisted cubes are \(4\)-pancyclic. Appl. Math. Lett. 17, 919–925 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  26. Dahbura, A.T., Masson, G.M.: An \(O(n^{2.5})\) faulty identification algorithm for diagnosable systems. IEEE Trans. Comput. 33(6), 486–492 (1984)

    Article  MATH  Google Scholar 

  27. Cheng, E., Lipták, L., Yang, W., Zhang, Z., Guo, X.: A kind of conditional vertex connectivity of Cayley graphs generated by \(2\)-trees. Inf. Sci. 181(19), 4300–4308 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  28. Hsieh, S.Y., Huang, H.W., Lee, C.W.: \(\{2, 3\}\)-restricted connectivity of locally twisted cubes. Theor. Comput. Sci. 615, 78–90 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  29. Li, X.J., Xu, J.M.: Generalized measures of fault tolerance in exchanged hypercubes. Inf. Process. Lett. 113(14–16), 533–537 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  30. Wei, C.C., Hsieh, S.Y.: \(h\)-restricted connectivity of locally twisted cubes. Discret. Appl. Math. 217, 330–339 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  31. Wan, M., Zhang, Z.: A kind of conditional vertex connectivity of star graphs. Appl. Math. Lett. 22(2), 264–267 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  32. Yang, W., Meng, J.X.: Generalized measures of fault tolerance in hypercube networks. Appl. Math. Lett. 25(10), 1335–1339 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  33. Fan, J., Zhang, S., Jia, X., Zhang, G.: The restricted connectivity of locally twisted cubes, In: Proceeding of International Symposium on Pervasive Systems, Algorithms, and Networks 2009, pp. 574–578

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Beijing Normal University Laboratory of Mathematics and Complex Systems, Ministry of Education, Beijing, 100875, China

    Yu-Long Wei & Min Xu

Authors
  1. Yu-Long Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Min Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Min Xu.

Additional information

This research was supported by the National Natural Science Foundation of China (Nos. 11571044 and 61373021) and the Fundamental Research Funds for the Central University of China.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wei, YL., Xu, M. The g-Good-Neighbor Conditional Diagnosability of Locally Twisted Cubes. J. Oper. Res. Soc. China 6, 333–347 (2018). https://doi.org/10.1007/s40305-017-0166-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-017-0166-2

Keywords

Mathematics Subject Classification

Search

Navigation