单圈图生成的凯莱图UGn在PMC模型和MM*模型下的1好邻诊断度

doi:10.15960/j.cnki.issn.1007-6093.2019.01.011

运筹学学报 ›› 2019, Vol. 23 ›› Issue (1): 97-103.doi: 10.15960/j.cnki.issn.1007-6093.2019.01.011

单圈图生成的凯莱图UG_n在PMC模型和MM^*模型下的1好邻诊断度

任佳敏¹, 冯伟¹, 赵凌琪², 王世英³, 吉日木图^1,*

1. 内蒙古民族大学数学学院, 内蒙古通辽 028043;
2. 内蒙古民族大学计算机科学与技术学院, 内蒙古通辽 028043;
3. 河南师范大学数学与信息科学学院, 河南新乡 453007

收稿日期:2017-09-11 出版日期:2019-03-15 发布日期:2019-03-15
通讯作者: 吉日木图 E-mail:jrmt@sina.com
基金资助:
国家自然科学基金（Nos.61262018，61370001，61402317），内蒙古民族大学科学研究项目（No.NMDGP17106）

The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model

REN Jiamin¹, FENG Wei¹, ZHAO Lingqi², WANG Shiying³, JIRIMUTU^1,*

1. College of Mathematics, Inner Mongolia University for Nationalities, Tongliao 028043, Inner Mongolia Autonomous Region, China;
2. College of Computer Science and Technology, Inner Mongolia University for Nationalities, Tongliao 028043, Inner Mongolia Autonomous Region, China;
3. School of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, Henan, China

Received:2017-09-11 Online:2019-03-15 Published:2019-03-15

摘要/Abstract

摘要：

多处理系统的诊断度是一个重要的研究课题.一种新的系统故障诊断方法称为g好邻诊断度，它是限制每个无故障点至少包含g个无故障的邻点.单圈图生成的凯莱图UG_n作为一种极好的互联网络拓扑结构有许多好的性质.现证明了当n ≥ 4时，单圈图生成的凯莱图UG_n在PMC模型下的1好邻诊断度是2n-1；当n ≥ 5时，UG_n在MM^*模型下的1好邻诊断度是2n-1.

关键词: 互联网络, 诊断度, 凯莱图, PMC模型, MM^*模型

Abstract:

Diagnosability of a multiprocessor system is an important study topic. A new measure for fault diagnosis of the system is called g-good-neighbor diagnosability that restrains every fault-free node containing at least g fault-free neighbors. As a famous topology structure of interconnection networks, the Cayley graph UG_n generated by unicyclic graphs has many good properties. In this paper, we prove that the 1-good-neighbor diagnosability of the Cayley graph UG_n generated by unicyclic graphs is 2n-1 under the PMC model for n ≥ 4; the 1-good-neighbor diagnosability of the Cayley graph UG_n generated by unicyclic graphs is 2n-1 under the MM^* model for n ≥ 5.

Key words: interconnection network, diagnosability, Cayley graph, PMC model, MM^* model

中图分类号:

O157.5

任佳敏, 冯伟, 赵凌琪, 王世英, 吉日木图. 单圈图生成的凯莱图UG_n在PMC模型和MM^*模型下的1好邻诊断度[J]. 运筹学学报, 2019, 23(1): 97-103.

REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU. The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model[J]. Operations Research Transactions, 2019, 23(1): 97-103.

参考文献

[1] Preparata F, Metze G, Chien R T. On the connection assignmemt problem of diagnosable systems[J]. IEEE Transactions on Electronic Computers, 1968, 12:848-854.
[2] Joon M, Miroslaw M. A comparision connection assignment for self-Diagnosis of multiprocessor systems[J]. Proceeding of 11th International Symposium on Fault-Tolerant Computing, 1981, 173-175.
[3] Lai P L, Tan J J M, Chang C P, et al. Conditional diagnosability measures for large multiprocessor systems[J]. IEEE Transactions on Computers, 2005, 54:165-175.
[4] Peng S L, Lin C K, Tan J J M, et al. The g-good-neighbor conditional diagnosability of hypercube under the PMC model[J]. Applied Mathematics Computation, 2012, 218:10406-10412.
[5] Wang S Y, Han W P. The g-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM^* model[J]. Information Processing Letters, 2016, 116:574-577.
[6] Yuan J, Liu A X, Ma X, et al. The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM^* model[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26:1165-1177.
[7] Wang M J J, Guo Y B, Wang S Y. The 1-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM^* model[J]. International Journal of Computer Mathematics, 2015, 23:1-12.
[8] Ma X L, Wang S Y, Wang Z H. The 1-good-neighbor connectivity and diagnosability of crossed cubes[J]. 应用数学进展, 2016, 5:282-290.
[9] Bai C, Wang S Y, Wang Z H. The 1-good-neighbor connectivity and diagnosability of Möbius cubes[J]. 应用数学进展, 2016, 5:728-737.
[10] Bondy J A, Murty U S R. Graph Theory[M]. New York:Springer, 2007.
[11] Song C Y, Huang Q X. The nullity of unicyclic graphs[J]. 运筹学学报, 2009, 13:77-83.
[12] Yu X M, Zhang Z. A kind of conditional connectivity of Cayley graphs generated by unicyclic graphs[J]. Information Science, 2013, 243:86-94.
[13] Cheng E, LiptSk L. Fault resiliency of Cayley graphs generated by transpositions[J]. International Journal of Foundations of Computer Science, 2007, 18:1005-1022.

单圈图生成的凯莱图UG_n在PMC模型和MM^*模型下的1好邻诊断度

The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

单圈图生成的凯莱图UGn在PMC模型和MM*模型下的1好邻诊断度

The 1-good-neighbor diagnosability of the Cayley graphs UGn generated by unicyclic graphs under the PMC model and the MM* model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

单圈图生成的凯莱图UG_n在PMC模型和MM^*模型下的1好邻诊断度

The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model