﻿ 交叉立方体的1好邻连通度和诊断度 The 1-Good-Neighbor Connectivity and Diagnosability of Crossed Cubes

Vol.05 No.02(2016), Article ID:17671,9 pages
10.12677/AAM.2016.52036

The 1-Good-Neighbor Connectivity and Diagnosability of Crossed Cubes

Xiaolei Ma1, Shiying Wang1,2*, Zhenhua Wang1

1School of Mathematics and Information Science, Henan Normal University, Xinxiang Henan

2Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang Henan

Received: May 4th, 2016; accepted: May 23rd, 2016; published: May 26th, 2016

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 containing 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.

Keywords:Interconnection Network, Graph, Diagnosability, Crossed Cube

1河南师范大学，数学与信息科学学院，河南 新乡

2河南师范大学，河南省大数据统计分析与优化控制工程实验室，河南 新乡

1. 引言

。原军等在文 [5] 中证明了k元n立方体在PMC模型和MM*模型下的g好邻诊断度是。在文 [6] 中，王牟江山等证明了网络的1好邻诊断度不超过条件诊断度。因此，研究网络的1好邻诊断度也是很有意义的。本文首先证明了交叉立方体的1好邻连通度是。然后，我们又证明了交叉立方体在PMC模型下的1好邻诊断度是和在MM*模型下的1好邻诊断度是

2. 预备知识

n维交叉立方体CQn [8] 有超立方体的正则性和相同的连通度。它是一个有2n个顶点和条边的n正则图。它包含长度为的圈，直径为大约是超立方体的一半。n维交叉立方体CQn的顶点u用长为n的二进制字符串表示，如，其中表示最高位，u0表示最低位。

n维交叉立方体CQn可以用递归定义表示：

(1) 如果n是偶数，

(2) 当时，

(1)

(2)

(3) 如果d是偶数，

(4) 当时，

(1)

Figure 1. The 4-dimensional crossed cube CQ4

(2) 如果n是偶数，

(3) 当时，

3. CQn 的1好邻连通度

4. CQn在PMC模型下的1好邻诊断度

。当时，上述不等式矛盾。

Figure 2. A distinguishable pair (F1, F2) under the PMC model

5. CQn在MM*模型下的1好邻诊断度

(1) 存在满足

(2) 存在满足

(3) 存在满足

Figure 3. A distinguishable pair (F1, F2) under the MM* model

。设W是中的孤立点集，。因此，当时，对任意的，存在个邻点在中。由于，故。因为，所以。假设，有。当时，上式矛盾。所以，。因为F1，F2不满足定理5.1中的(1)且的任意一点在H中不是孤立点，所以之间不存在边相连。因此，是CQn的点割且，即是CQn的一个1好邻割。根据定理3.6，。 因为都非空，所以。于是，设。故对于任意的满足。根据引理3.1，v1与v2至多有两个公共邻点。因此，至多有两个孤立点。

，则。因为F2是一个1好邻故障集，所以没有孤立点。断言1证明完毕。

。根据断言1，u在中至少有一个邻点。因为F1，F2不满足定理5.1，根据定理5.1(1)，所以对于任意一对相邻的点，不存在使得

Figure 4. CQ4 is not 1-good-neighbor 7-diagnosable

。因此，u在中没有邻点。由u的任意性，中间没有边。因为F1是一个1好邻故障集且，所以。根据引理4.5，。因为F1和F2都是1好邻故障集且之间没有边，所以是CQn的一个1好邻割。根据定理3.6，。因此，。这与矛盾。于是，CQn是一个1好邻-可诊断的。故

6. 结束语

The 1-Good-Neighbor Connectivity and Diagnosability of Crossed Cubes[J]. 应用数学进展, 2016, 05(02): 282-290. http://dx.doi.org/10.12677/AAM.2016.52036

1. 1. 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.

2. 2. 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.

3. 3. 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. http://dx.doi.org/10.1109/TC.2005.19

4. 4. 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. http://dx.doi.org/10.1016/j.amc.2012.03.092

5. 5. 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. http://dx.doi.org/10.1109/TPDS.2014.2318305

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

7. 7. Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.

8. 8. Efe, K. (1992) The Crossed Cube Architecture for Parallel Computation. IEEE Transactions on Parallel and Distributed Systems, 3, 513-524. http://dx.doi.org/10.1109/71.159036