The 1-Good-Neighbor Connectivity and Diagnosability of Crossed Cubes
Abstract: Connectivity and diagnosability are important parameters in measuring the fault diagnosis of multiprocessor systems. In 2012, Peng et al. proposed a new measure for fault diagnosis of the system, which is called g-good-neighbor diagnosability that restrains every fault-free node con-taining at least g fault-free neighbors. The n-dimensional crossed cube is an important variant of the hypercube. In this paper, we prove that the 1-good-neighbor connectivity of crossed cube is 2n − 2 for n ≥ 4, and the 1-good-neighbor diagnosability of crossed cube is 2n − 1 under the PMC model for n ≥ 4 and the MM* model for n ≥ 5.
文章引用: 马晓蕾 , 王世英 , 王贞化 (2016) 交叉立方体的1好邻连通度和诊断度。 应用数学进展， 5， 282-290. doi: 10.12677/AAM.2016.52036
 Preparata, F., Metze, G. and Chien, R.T. (1968) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, 12, 848-854.
 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.
Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Di-agnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175.
Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under the PMC Model. Applied Mathematics Computation, 218, 10406-10412.
Yuan, J., Liu, A.X., Ma, X., Liu, X.L., Qin, X. and Zhang, J.F. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177.
 Wang, M.J.S., Guo, Y.B. and Wang, S.Y. (2015) The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics.
 Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.
Efe, K. (1992) The Crossed Cube Architecture for Parallel Computation. IEEE Transactions on Parallel and Distributed Systems, 3, 513-524.