Research ArticleOpen AccessGoogle Scholar indexed
The Tightly Super 3-Extra Connectivity and Diagnosability of Locally Twisted Cubes
School of Electrical Engineering and Computer Science, The University of Newcastle, Newcastle, NSW, Australia
School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan, China
School of Electrical Engineering and Computer Science, The University of Newcastle, Newcastle, NSW, Australia
School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan, China
- 1 School of Electrical Engineering and Computer Science, The University of Newcastle, Newcastle, NSW, Australia
- 2 School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan, China
- 3 School of Electrical Engineering and Computer Science, The University of Newcastle, Newcastle, NSW, Australia
- 4 School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan, China
American Journal of Computational Mathematics·Volume 07 (2017)·Pages 127–144·Published 8 June 2017·DOI10.4236/ajcm.2017.72011
Copy link · social · email
Abstract
Diagnosability of a multiprocessor system G is one important measure of the reliability of interconnection networks. In 2016, Zhang <i> et al </i> . proposed the <i> g </i>- extra diagnosability of <i> G </i> , which restrains that every component of <i> G – S</i> has at least (g + 1) vertices. The locally twisted cube <i> LTQ<sub>n</sub></i> is applie d widely. In this paper, we show that <i> LTQ<sub>n</sub></i> is tightly (4n – 9) super 3-extra connected for n ≥ 6 and the 3-extra diagnosability of <i> LTQ<sub>n</sub></i> under the PMC model and MM * model is 4n - 6 for n ≥ 5 and n ≥ 7 , respectively.
KeywordsInterconnection NetworkCombinatoricsDiagnosability
- Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers, EC-16, 848-854. https://doi.org/10.1109/PGEC.1967.264748
- Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, 173-175.
- Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. https://doi.org/10.1109/12.177309
- Fàbrega, J. and Fiol, M.A. (1996) On the Extraconnectivity of Graphs. Discrete Mathematics, 155, 49-57.
- Gu, M.-M., Hao, R.-X. and Liu J.-B. (2017) On the Extraconnectivity of k-Ary n-Cube Networks. International Journal of Computer Mathematics, 94, 95-106. https://doi.org/10.1080/00207160.2015.1091070
- Chang, N.-W., Tsai, C.-Y. and Hsieh, S.-Y. (2014) On 3-Extra Connectivity and 3-Extra Edge Connectivity of Folded Hypercubes. IEEE Transactions on Computers, 63, 1593-1599.
- Zhang, M.-M. and Zhou, J.-X. (2015) On g-Extra Connectivity of Folded Hypercubes. Theoretical Computer Science, 593, 146-153.
- Hsieh, S.-Y. and Chang, Y.-H. (2012) Extraconnectivity of k-Ary n-Cube Networks. Theoretical Computer Science, 443, 63-69.
- Gu, M.-M. and Hao, R.-X. (2014) 3-Extra Connectivity of 3-Ary n-Cube Networks. Information Processing Letters, 114, 486-491.
- Lin, R.Z. and Zhang, H.P. (2016) The Restricted Edge-Connectivity and Restricted Connectivity of Augmented k-Ary n-Cubes. International Journal of Computer Mathematics, 93, 1281-1298. https://doi.org/10.1080/00207160.2015.1067690
- Lü, H. (2017) On Extra Connectivity and Extra Edge-Connectivity of Balanced Hypercubes. International Journal of Computer Mathematics, 94, 813-820. https://doi.org/10.1080/00207160.2016.1148813
- Hong, W.-S. and Hsieh, S.-Y. (2013) Extra Edge Connectivity of Hypercube-Like Networks. International Journal of Parallel, Emergent and Distributed Systems, 28, 123-133. https://doi.org/10.1080/17445760.2011.650696
- Xu, J.M., Wang, J.W. and Wang, W.W. (2010) On Super and Restricted Connectivity of Some Interconnection Networks. Ars Combinatoria, 94, 1-8.
- Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412. https://doi.org/10.1016/j.amc.2012.03.092